Submission #1033896

#TimeUsernameProblemLanguageResultExecution timeMemory
1033896denislavDEL13 (info1cup18_del13)C++17
15 / 100
4 ms1368 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<<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]; void solve() { if(n==q) {cout<<0<<"\n";return ;} vector<pair<int,int>> len; vector<int> sz; 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(); for(int i=0;i<m;i++) { sz.push_back(len[i].second-len[i].first+1); 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 ;} if(sz[0]%2!=sz[1]%2) {cout<<-1<<"\n";return ;} doit(len[0].first,len[0].second); doit(len[1].first,len[1].second); int mid=len[0].second+1; if(sz[0]%2==0) {v.push_back(mid);v.push_back(mid);} else v.push_back(mid); print_moves(); } void reset() { v.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 */
#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...