Submission #1033996

#TimeUsernameProblemLanguageResultExecution timeMemory
1033996denislavDEL13 (info1cup18_del13)C++17
0 / 100
4 ms1372 KiB
# include <iostream> # include <vector> using namespace std; const int MAX=2e5+11; int n,q,m; int a[MAX]; bool used[MAX]; vector<int> v; void read() { cin>>n>>q; for(int i=1;i<=q;i++) { cin>>a[i]; used[a[i]]=1; } } void print_moves() { cout<<0<<"\n"; /* cout<<v.size()<<"\n"; for(int x: v) cout<<x<<" "; cout<<"\n"; */ } void doit(int l, int r) { //cout<<l<<" "<<r<<"\n"; int sz=(r-l+1); int cut=(l+r)/2; while(sz>2) { sz-=2; v.push_back(cut); } } bool alone[MAX]; bool f=1; vector<pair<int,int>> len; void doit2(vector<pair<int, int>> curr) { vector<bool> rem(curr.size()); for(int i=0;i<(int)curr.size()-1;i++) { //cout<<"->"<<curr[i].first<<" "<<curr[i].second<<"\n"; //if(i==0) cout<<"-->"<<curr[i+1].first<<" "<<curr[i+1].second<<"\n"; if(curr[i].second<0) {f=0;return ;} if(rem[i]==1 and rem[i]%2==0) continue; if(curr[i].second%2==0) { rem[i]=1; rem[i+1]=1; curr[i].second-=2; curr[i+1].second-=2; } else { rem[i]=1; rem[i+1]=1; curr[i].second--; curr[i+1].second--; } if(curr[i].second<0) {f=0;return ;} } int sz=curr.size()-1; if(curr[sz].second<0) {f=0;return ;} if(rem[sz] and curr[sz].second%2==0) return ; if(curr[sz].second%2==0) { if(curr[sz-1].second%2==0) { if(curr[sz-1].second>=2 and curr[sz].second>=2) return ; else {f=0;return ;} } else {f=0;return ;} } else { if(curr[sz-1].second%2!=0) { if(curr[sz-1].second>=1 and curr[sz].second>=1) return ; else {f=0;return ;} } } //cout<<"\n"; } void solve() { if(n==q) {cout<<0<<"\n";return ;} int start=-1; for(int i=1;i<=n;i++) { if(used[i]==0) { if(start==-1) start=i; } else { if(start!=-1) len.push_back({start,i-1}); start=-1; } } if(start!=-1) len.push_back({start,n}); int m=len.size(); vector<int> sz; for(int i=0;i<m;i++) { //cout<<i<<":"<<len[i].first<<" "<<len[i].second<<"\n"; //doit(len[i].first,len[i].second); //int p=(len[i].second-len[i].first+1)%2; //if(p==0) p+=2; sz.push_back(len[i].second-len[i].first+1); //cout<<sz.back()<<"\n"; if(i>0 and len[i-1].second+2==len[i].first) { alone[i-1]=0; alone[i]=0; } } for(int i=0;i<m;i++) if(alone[i]) {cout<<-1<<"\n";return ;} vector<pair<int, int>> curr; for(int i=0;i<m;i++) { if(i>0 and len[i-1].second+2==len[i].first) { curr.push_back({i,sz[i]}); } else { if((int)curr.size()>0) doit2(curr); curr.clear(); curr.push_back({i,sz[i]}); } } if((int)curr.size()>0) doit2(curr); if(f) print_moves(); else cout<<-1<<"\n"; } void reset() { f=1; v.clear(); len.clear(); for(int i=1;i<=n;i++) used[i]=0; for(int i=0;i<=n;i++) alone[i]=1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t; cin>>t; while(t--) { reset(); read(); solve(); } return 0; } /** 3 5 1 3 7 3 1 5 7 7 3 1 2 7 */ /** 1 5 1 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...