Submission #821731

#TimeUsernameProblemLanguageResultExecution timeMemory
821731PVM_pvmWatermelon (INOI20_watermelon)C++17
38 / 100
2074 ms3400 KiB
#include<bits/stdc++.h> using namespace std; #define MAXX 100007 #define MAXN 13 int b[MAXX],b2[MAXX],n,k; struct perm { int ch[MAXN]; perm(int a[]) { for (int q=1;q<=n;q++) ch[q]=a[q]; } void show() { //cout<<"P:"; for (int q=1;q<=n;q++) cout<<ch[q]<<" "; cout<<"\n"; } }; vector<perm> ans; int cur[MAXN],sb[MAXN]; bool dt[MAXN]; void check() { for (int q=1;q<=n;q++) sb[q]=-1; for (int q=1;q<=n;q++) dt[q]=false; for (int tm=1;true;tm++) { bool smyrt=false; for (int q=1;q<=n;q++) { if (dt[q]) continue; int next=q+1; for (next=q+1;next<=n;next++) { if (!dt[next]) break; } if (next>n) break; if (cur[next]>cur[q]) { dt[q]=true; smyrt=true; sb[q]=tm; } } if (!smyrt) break; } bool pr=true; for (int q=1;q<=n;q++) { if (sb[q]!=b[q]) pr=false; } if (pr) { perm spr(cur); ans.push_back(spr); } } int ind[MAXN]; int ind2[MAXN]; bool cmp(perm &a, perm &b){ for (int q=1;q<=n;q++) { ind[a.ch[q]] = q; ind2[b.ch[q]] = q; } for (int q=1;q<=n;q++) { if (ind[q] < ind2[q]) return 1; if (ind[q] > ind2[q]) return 0; } return 0; } int ansk[MAXX]; int pr1[MAXX]; int chb[MAXX]; int posOfLST[MAXX]; int bfMe[MAXX]; bool finalcheck() { stack<pair<int,int>> st; chb[n]=-1; //if (chb[n]!=b[n]) return false; st.push({ansk[n],n}); for (int q=n-1;q>=1;q--) { chb[q]=-2; while (true) { if (st.empty()) { chb[q]=-1; st.push({ansk[q],q}); break; } int chislo = st.top().first; int pos = st.top().second; if (ansk[q]>chislo) { chb[q]=max(chb[q],chb[pos]); st.pop(); continue; } if (chb[q]==-2) chb[q]=1; else chb[q]++; st.push({ansk[q],q}); break; } //cout<<q<<":"<<chb[q]<<" "<<b[q]<<"\n"; //if (chb[q]!=b[q]2) return false; } for (int q=1;q<=n;q++) { if (chb[q]!=b2[q]) return false; } return true; } int lf[MAXN],rf[MAXN]; void printthem() { for (int q=1;q<=n;q++) { cout<<ansk[q]<<" "; } cout<<"\n"; } void getSecond() { int lst=0; for (int q=1;q<=n;q++) { if (b[q]==-1) { lf[q]=lst; } if (b[q]==1) { lst=q; } } lst=0; for (int q=n;q>=1;q--) { if (b[q]==-1) { rf[q]=lst; } if (b[q]==1) { lst=q; } } int pos=0; for (int q=1;q<=n;q++) { if (lf[q]!=0) { pos=q; break; } } if (pos==0) { cout<<"-1\n"; return; } if (b[n-1]==-1) { int ch=ansk[n]; int hpos=0; for (int q=1;q<=n;q++) { if (ansk[q]==ch-1) { hpos=q; } } swap(ansk[hpos],ansk[n]); printthem(); return; } int f1=0; for (int q=n;q>=1;q--) { if (b[q]==1) { f1=q; break; } } int f2=0; for (int q=f1;q>=1;q--) { if (b[q]!=1) break; f2=q; } bool ima=false; bool ima1=false; bool minahminus=false; int ngc=0,kdc=0; for (int q=f1-1;q>=1;q--) { if (b[q]>1 && !minahminus) ima=true; if (b[q]==1 && !minahminus) ima1=true; if (b[q]==-1) minahminus=true; if (b[q]!=-1 && minahminus) { if (ansk[q]>ngc) { ngc=ansk[q]; kdc=q; } } } if (ima && ima1) { int ng=0,kd=0; for (int q=f1-1;q>=1;q--) { if (b[q]==-1) break; if (ansk[q]>ng && ansk[q]<ansk[f2]) { ng=ansk[q]; kd=q; } } if (ng!=0) { swap(ansk[f2],ansk[kd]); printthem(); return; } } if (ngc==0) { cout<<"-1\n"; return; } swap(ansk[f2],ansk[kdc]); printthem(); } int main() { cin>>n>>k; if (k!=1 && k!=2) { for (int q=1;q<=n;q++) cin>>b[q]; for (int q=1;q<=n;q++) cur[q]=q; check(); while (next_permutation(cur+1,cur+n+1)) check(); sort(ans.begin(),ans.end(),cmp); if (k<ans.size()) ans[k-1].show(); else cout<<"-1\n"; return 0; } if (k==1) { for (int q=1;q<=n;q++) cin>>b[q]; for (int q=1;q<=n;q++) b2[q]=b[q]; int br2=0; for (int q=1;q<=n;q++) { if (b[q]!=-1) br2++; } if (b[n]==-1) posOfLST[n+2]=n; else posOfLST[b[n]]=n; for (int q=n-1;q>=1;q--) { if (b[q]==-1) continue; if (b[q]==1) {posOfLST[b[q]]=q;continue;} int pos=posOfLST[b[q]-1]; if (pos==0) { cout<<"-1\n"; return 0; } if (bfMe[pos]!=0) { cout<<"-1\n"; return 0; } bfMe[pos]=q; posOfLST[b[q]]=q; } int dok=1; for (int q=1;q<=n;q++) { if (b[q]==1) { ansk[q]=dok; //cout<<q<<" "<<dok<<"\n"; dok++; int w=bfMe[q]; while (w!=0) { ansk[w]=dok; //cout<<w<<" "<<dok<<"\n"; dok++; w=bfMe[w]; } } } int tm=n; for (int q=1;q<=n;q++) { if (ansk[q]==0) { ansk[q]=tm; tm--; } } if (finalcheck()) { for (int q=1;q<=n;q++) { cout<<ansk[q]<<" "; } cout<<"\n"; } else { cout<<"-1\n"; } } else { for (int q=1;q<=n;q++) cin>>b[q]; for (int q=1;q<=n;q++) b2[q]=b[q]; int br2=0; for (int q=1;q<=n;q++) { if (b[q]!=-1) br2++; } if (b[n]==-1) posOfLST[n+2]=n; else posOfLST[b[n]]=n; for (int q=n-1;q>=1;q--) { if (b[q]==-1) continue; if (b[q]==1) {posOfLST[b[q]]=q;continue;} int pos=posOfLST[b[q]-1]; if (pos==0) { cout<<"-1\n"; return 0; } if (bfMe[pos]!=0) { cout<<"-1\n"; return 0; } bfMe[pos]=q; posOfLST[b[q]]=q; } int dok=1; for (int q=1;q<=n;q++) { if (b[q]==1) { ansk[q]=dok; //cout<<q<<" "<<dok<<"\n"; dok++; int w=bfMe[q]; while (w!=0) { ansk[w]=dok; //cout<<w<<" "<<dok<<"\n"; dok++; w=bfMe[w]; } } } int tm=n; for (int q=1;q<=n;q++) { if (ansk[q]==0) { ansk[q]=tm; tm--; } } if (finalcheck()) { getSecond(); } else { cout<<"-1\n"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:252:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<perm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |         if (k<ans.size()) ans[k-1].show();
      |             ~^~~~~~~~~~~
#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...