# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
689817 | 2023-01-29T12:33:42 Z | alexdd | DEL13 (info1cup18_del13) | C++17 | 50 ms | 2584 KB |
#include<bits/stdc++.h> using namespace std; #define int long long int n,q; int v[100005]; int gap[100005]; vector<int> sol; vector<int> sol2; signed main() { ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--) { sol.clear(); sol2.clear(); for(int i=0;i<100005;i++) gap[i]=0; cin>>n>>q; for(int i=1;i<=q;i++) { cin>>v[i]; gap[i-1]=v[i]-v[i-1]-1; } if(q==0) { cout<<-1<<"\n"; continue; } gap[q] = n - v[q]; q++; v[q] = n+1; bool impossible=0; for(int i=1;i<q;i++) { if(impossible) break; if(gap[i-1]==0 || gap[i]==0) continue; if(gap[i-1]%2==1 && gap[i]>=1 && gap[i-1]>=1)///daca trebuie sa scad 1 { sol.push_back(v[i]); gap[i]--; gap[i-1]--; } } for(int i=0;i<q;i++) if(gap[i]%2==1) impossible=1; int inc = 0; for(int i=0;i<=q;i++) { if(impossible) break; if(gap[i]==0) { if(inc!=i) { if((i-inc)%2==0) { for(int j=inc;j<i;j+=2) { sol.push_back(v[j+1]); sol.push_back(v[j+1]); gap[j]-=2; gap[j+1]-=2; } } else { int mxm=0,unde=-1; bool avem=0; int unde_avem=-1; for(int j=inc;j<i;j++) { if((j-inc)%2==0 && gap[j]!=v[j+1]-v[j]-1) { avem=1; unde_avem=j; } if(j>inc && j<i-1 && gap[j]>=4 && (j-inc)%2==1) { mxm=gap[j]; unde=j; } } if(avem) { int cate=0; for(int j=inc;j<i;j++) { if(j!=unde_avem) cate++; if(cate%2==1) { sol.push_back(v[j+1]); sol.push_back(v[j+1]); gap[j]-=2; gap[j+1]-=2; } } } else { if(mxm<4) impossible=1; else { for(int j=unde;j<i;j+=2) { sol.push_back(v[j+1]); sol.push_back(v[j+1]); gap[j]-=2; gap[j+1]-=2; } for(int j=inc;j<unde;j+=2) { sol.push_back(v[j+1]); sol.push_back(v[j+1]); gap[j]-=2; gap[j+1]-=2; } } } } } inc=i+1; } } if(!impossible) { for(int i=0;i<q;i++) { if(gap[i]==0) continue; if(gap[i]<0 || gap[i]%2==1 || gap[i]==v[i+1]-v[i]-1) { impossible=1; break; } int mij=(v[i+1]+v[i])/2; while(gap[i]>0) { sol2.push_back(mij); gap[i]-=2; } } } if(impossible) { cout<<-1<<"\n"; continue; } cout<<sol.size() + sol2.size()<<"\n"; for(int i=0;i<sol2.size();i++) cout<<sol2[i]<<" "; for(int i=0;i<sol.size();i++) cout<<sol[i]<<" "; cout<<"\n"; } return 0; } /** cazuri pe care nu merge solutia: 1 20 6 4 12 15 18 19 20 my solution: -1 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 980 KB | Output is correct |
2 | Correct | 10 ms | 1108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 980 KB | Output is correct |
2 | Correct | 10 ms | 1108 KB | Output is correct |
3 | Correct | 50 ms | 1104 KB | Output is correct |
4 | Correct | 48 ms | 1120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 1236 KB | Output is correct |
2 | Correct | 6 ms | 1108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 980 KB | Output is correct |
2 | Correct | 10 ms | 1108 KB | Output is correct |
3 | Correct | 50 ms | 1104 KB | Output is correct |
4 | Correct | 48 ms | 1120 KB | Output is correct |
5 | Correct | 3 ms | 1108 KB | Output is correct |
6 | Correct | 2 ms | 1108 KB | Output is correct |
7 | Correct | 2 ms | 1012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 980 KB | Output is correct |
2 | Correct | 10 ms | 1108 KB | Output is correct |
3 | Correct | 50 ms | 1104 KB | Output is correct |
4 | Correct | 48 ms | 1120 KB | Output is correct |
5 | Correct | 3 ms | 1108 KB | Output is correct |
6 | Correct | 2 ms | 1108 KB | Output is correct |
7 | Correct | 2 ms | 1012 KB | Output is correct |
8 | Correct | 9 ms | 1236 KB | Output is correct |
9 | Correct | 8 ms | 1364 KB | Output is correct |
10 | Correct | 8 ms | 1460 KB | Output is correct |
11 | Correct | 15 ms | 2584 KB | Output is correct |