CF1023D Array Restoration

思路：

使用set即可，细节很多，容易出错。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 int a[MAXN], l[MAXN], r[MAXN];

 int main()

 {

     int n, q;

     while (cin >> n >> q)

     {

         for (int i = ; i <= q; i++) { l[i] = INF; r[i] = -INF; }

         int c0 = , cq = ;

         for (int i = ; i <= n; i++)

         {

             cin >> a[i];

             c0 += a[i] == ;

             cq += a[i] == q;

             if (a[i] == ) continue;

             l[a[i]] = min(l[a[i]], i);

             r[a[i]] = max(r[a[i]], i);

         }

         if (!c0 && !cq) { cout << "NO" << endl; continue; }

         set<int> st;

         bool flg = true;

         for (int i = ; i <= n; i++)

         {

             if (i == l[a[i]]) st.insert(a[i]);

             if (a[i] && !st.empty() && *st.rbegin() != a[i]) { flg = false; break; }

             int tmp = -;

             if (a[i] == )

             {

                 if (cq == ) { tmp = q; cq++; }

                 else if (!st.empty()) tmp = *st.rbegin();

                 else tmp = ;

             }

             if (i == r[a[i]]) st.erase(st.find(a[i]));

             if (tmp != -) a[i] = tmp;

         }

         if (!cq || !flg) { cout << "NO" << endl; continue; }

         cout << "YES" << endl;

         for (int i = ; i <= n; i++) cout << a[i] << " ";

         cout << endl;

     }

     return ;

 }