In the editorial, they use prefix sums to find the MEXs, but we can actually calculate the final MEX of the subsegments directly. This is based on the fact that if an element is in the array, there MUST be a subsegment that does NOT have it as the MEX. Thus, the final MEX(for all subsegments) must be just the MEX of the original array. With this knowledge we can simply find the first subsegment with that MEX as the MEX. From there, we look for one more subsegment with this as the MEX, if found, we are done. If not, we know it must be impossible. Please note this is my first real blog, let me know if I did something wrong.↵
↵
Code:↵
~~~~~↵
Your code here...#include <bits/stdc++.h>↵
#define int long long↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define vii vector<pair<int,int>>↵
↵
using namespace std;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
int a[n];↵
set<int> s;↵
for(int i=0;i<n;i++){↵
cin >> a[i];↵
s.insert(a[i]);↵
}↵
int MEX=0;↵
while(true){↵
if(s.find(MEX) != s.end()){↵
MEX++;↵
}↵
else{↵
break;↵
}↵
}↵
s.clear();↵
for(int i=0;i<MEX;i++){↵
s.insert(i);↵
}↵
int r=0;↵
for(int i=0;i<n;i++){↵
s.erase(a[i]);↵
if(s.empty()){↵
for(int i=0;i<MEX;i++){↵
s.insert(i);↵
}↵
break;↵
} else{↵
r++;↵
}↵
}↵
for(int i=r+1;i<n;i++){↵
s.erase(a[i]);↵
if(s.empty()){↵
cout << 2 << "\n1 " << r+1 << "\n" << r+2 << " " << n << "\n";↵
return;↵
}↵
}↵
cout << -1 << "\n";↵
}↵
↵
signed main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~https://codeforces.me/contest/1935/submission/282863993↵
↵
↵
↵
↵
↵
Code:↵
Your code here...#include <bits/stdc++.h>↵
#define int long long↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define vii vector<pair<int,int>>↵
↵
using namespace std;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
int a[n];↵
set<int> s;↵
for(int i=0;i<n;i++){↵
cin >> a[i];↵
s.insert(a[i]);↵
}↵
int MEX=0;↵
while(true){↵
if(s.find(MEX) != s.end()){↵
MEX++;↵
}↵
else{↵
break;↵
}↵
}↵
s.clear();↵
for(int i=0;i<MEX;i++){↵
s.insert(i);↵
}↵
int r=0;↵
for(int i=0;i<n;i++){↵
s.erase(a[i]);↵
if(s.empty()){↵
for(int i=0;i<MEX;i++){↵
s.insert(i);↵
}↵
break;↵
} else{↵
r++;↵
}↵
}↵
for(int i=r+1;i<n;i++){↵
s.erase(a[i]);↵
if(s.empty()){↵
cout << 2 << "\n1 " << r+1 << "\n" << r+2 << " " << n << "\n";↵
return;↵
}↵
}↵
cout << -1 << "\n";↵
}↵
↵
signed main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~
↵
↵
↵
↵
