Problem A
meda
plain_text
2 months ago
2.7 kB
3
Indexable
#include<bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; template<class T> void printff(vector<T>& v) { for (auto k : v) cout << k << " "; cout << endl; } void SOLVE() { int n; cin >> n; vector<int> a(n), freq(n + 3); for(auto & val : a) cin >> val, freq[val]++; int mex = 0; for(int i = 0; i <= n + 2; i++){ if(!freq[i]){ mex = i; break; } } if(mex == 0){ for(int i = n + 2; i >= 0; i--){ if(freq[i] >= 2){ freq[0]++; freq[i]--; break; } } if(!freq[0]){ for(int i = n + 2; i >= 0; i--){ if(freq[i]){ freq[0]++; freq[i]--; break; } } } int answer = 0; for(int i = 0; i <= n + 2; i ++){ if(!freq[i]) return void(cout << i << endl); } }else{ for(int i = 0; i < mex; i++){ if(freq[i] < 2) return void(cout << mex << endl); } vector<pair<int, int>> segs; vector<int> f(mex + 1); int l = 0, r = 0; int counter = 0; if(a[l] < mex) f[a[l]]++, counter++; while(r < n){ r++; if(r < n && a[r] < mex){ f[a[r]]++; if(f[a[r]] == freq[a[r]]){ while(f[a[r]] == freq[a[r]]){ if(a[l] >= mex){ l++; continue; } f[a[l]]--; if(f[a[l]] == 0) counter--; l++; } }else if(f[a[r]] == 1){ counter++; } } while(counter == mex){ while(l < n && a[l] >= mex){ l++; } segs.push_back({l, r}); f[a[l]]--; if(f[a[l]] == 0) counter--; l++; } } auto solve =[&](int l, int r){ vector<int> ff(n + 2); for(int i = l; i <= r; i++){ ff[a[i]]++; } int m; for(int i = 0; i <= n + 1; i++){ if(!ff[i]){ m = i; break; } } if(m != mex) return mex; vector<int> temp = a; for(int i = l; i <= r; i++){ temp[i] = m; } for(int i = 0; i < n; i++){ ff[temp[i]]++; } for(int i = 0; i <= n + 1; i++){ if(!ff[i]) return i; } }; int mx = mex; for(int i = 0; i < segs.size(); i++){ mx = max(mx, solve(segs[i].first, segs[i].second)); } cout << mx << endl; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int tc = 1; //cin >> tc; while(tc--) SOLVE(); return 0; }
Editor is loading...
Leave a Comment