Submission #1034098

#TimeUsernameProblemLanguageResultExecution timeMemory
1034098denislavDEL13 (info1cup18_del13)C++17
6 / 100
5 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"; */ } int doit(int l, int r) { //cout<<l<<" "<<r<<"\n"; int sz=(r-l+1); int cut=(l+r)/2; while(sz>4) { sz-=2; v.push_back(cut); } return sz; } bool alone[MAX]; bool f=1; vector<pair<int,int>> len; bool dp[MAX][6][2]; void doit2(vector<pair<int, int>> curr) { int sz=curr.size(); for(int i=0;i<sz;i++) { for(int k=0;k<=4;k++) { dp[i][k][0]=dp[i][k][1]=0; } } dp[0][curr[0].second][0]=1; for(int i=0;i<sz-1;i++) { for(int f=0;f<=1;f++) { for(int k=0;k<=4;k++) { if(dp[i][k][f]==0) continue; if(f==0 or (f==1 and k%2!=0)) { if(k%2==1) { if(k>=1 and curr[i+1].second>=1) dp[i+1][curr[i+1].second-1][1]=1; } else if(k%2==0) { if(k>=2 and curr[i+1].second>=2) dp[i+1][curr[i+1].second-2][1]=1; } } else if(f==1) { dp[i+1][curr[i+1].second][0]=1; if(curr[i+1].second>=1 and k>=1) dp[i+1][curr[i+1].second-1][1]=1; if(curr[i+1].second>=2 and k>=2) dp[i+1][curr[i+1].second-2][1]=1; } } } } if(!(dp[sz-1][0][1] or dp[sz-1][2][1] or dp[sz-1][4][1])) f=0; return ; } 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(doit(len[i].first,len[i].second)); //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...