CF R767 C. Meximum Array

Problem.

https://codeforces.com/contest/1629/problem/C

Idea.

Find mex for all suffix a[i:n-1]
Split the array greedily.

Source.

 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           int n; cin >> n;  
           vector<int> a(n);  
           REP(i, n) cin >> a[i];  
           // find all suffix mex a[i:n-1]  
           vector<int> mex(n);  
           vector<int> cnt(n + 10, 0);  
           int now = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                cnt[a[i]]++;  
                if (a[i] == now) {  
                     while (cnt[now]) now++;  
                }  
                mex[i] = now;  
           }  
           // split the array  
           vector<int> ret;  
           int cur = 0;  
           while (cur < n) {  
                ret.push_back(mex[cur]);  
                int i = cur;  
                set<int> st;  
                while (i < n) {  
                     if (a[i] < mex[cur]) st.insert(a[i]);  
                     if (st.size() == mex[cur]) break;  
                     i++;  
                }  
                cur = i + 1;  
           }  
           cout << ret.size() << endl;  
           for (int x : ret) cout << x << " "; cout << endl;  
      }  
 }