fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int M = 1e9 + 7;
  5.  
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(NULL);
  10.     int n;
  11.     cin >> n;
  12.     vector<int> v(n);
  13.     for (int i = 0; i < n; i++)
  14.         cin >> v[i];
  15.     unordered_map<int, int> suffix;
  16.     for (int i = n - 1; i >= 0; i--)
  17.     {
  18.         suffix[v[i]]++;
  19.     }
  20.     int cnt = 0;
  21.     unordered_set<int> prefix;
  22.     vector<int> ans;
  23.     for (int i = 0; i < n; i++)
  24.     {
  25.         prefix.insert(v[i]);
  26.         while (prefix.find(cnt) != prefix.end())
  27.             cnt++;
  28.         if (suffix.find(cnt) == suffix.end())
  29.         {
  30.             if (i == n - 1)
  31.                 break;
  32.             ans.push_back(cnt);
  33.             prefix.clear();
  34.             cnt = 0;
  35.         }
  36.         suffix[v[i]]--;
  37.         if (suffix[v[i]] == 0)
  38.             suffix.erase(v[i]);
  39.     }
  40.     ans.push_back(cnt);
  41.  
  42.     for (auto it : ans)
  43.         cout << it << " ";
  44.     return 0;
  45. }
  46.  
  47.  
  48.  
  49. // 9
  50. // 2 2 3 4 0 1 2 0 0
  51.  
  52. // 15
  53. // 0 1 2 3 0 1 2 3 4 0 1 2 0 2 1
  54.  
  55.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
9
2 2 3 4 0 1 2 0 0
stdout 
5 1 1
https://ideone.com/LZmeGZ
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!