Submission #821512

#TimeUsernameProblemLanguageResultExecution timeMemory
821512PVM_pvmWatermelon (INOI20_watermelon)C++17
38 / 100
2077 ms3788 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; }/* struct node { int sm; int pos; int lz; } seg[4*MAXX]; void Initialise(int ind, int l, int r) { if (l==r) { if (b[l]==-1) { seg[ind].sm=n*2; } else { seg[ind].sm=b[l]; } seg[ind].pos=l; seg[ind].lz=0; return; } int mid=(l+r)/2; Initialise(ind*2,l,mid); Initialise(ind*2+1,mid+1,r); if (seg[ind*2].sm<=seg[ind*2+1].sm) { seg[ind].sm=seg[ind*2].sm; seg[ind].pos=seg[ind*2].pos; } else { seg[ind].sm=seg[ind*2+1].sm; seg[ind].pos=seg[ind*2+1].pos; } seg[ind].lz=0; } void Push(int ind, int l, int r) { if (seg[ind].lz==0) return; seg[ind].sm-=seg[ind].lz; if (l!=r) { seg[ind*2].lz+=seg[ind].lz; seg[ind*2+1].lz+=seg[ind].lz; } seg[ind].lz=0; } void Update(int ind, int l, int r, int ql, int qr) { Push(ind,l,r); if (l>=ql && r<=qr) { seg[ind].lz++; Push(ind,l,r); return; } int mid=(l+r)/2; if (ql<=mid) Update(ind*2,l,mid,ql,qr); if (qr>=mid+1) Update(ind*2+1,mid+1,r,ql,qr); Push(ind*2,l,mid); Push(ind*2+1,mid+1,r); if (seg[ind*2].sm<=seg[ind*2+1].sm) { seg[ind].sm=seg[ind*2].sm; seg[ind].pos=seg[ind*2].pos; } else { seg[ind].sm=seg[ind*2+1].sm; seg[ind].pos=seg[ind*2+1].pos; } } void UpdateCh(int ind, int l, int r, int pos) { Push(ind,l,r); if (l==r && l==pos) { seg[ind].sm=n*2; seg[ind].pos=l; seg[ind].lz=0; return; } int mid=(l+r)/2; if (pos<=mid) UpdateCh(ind*2,l,mid,pos); if (pos>=mid+1) UpdateCh(ind*2+1,mid+1,r,pos); Push(ind*2,l,mid); Push(ind*2+1,mid+1,r); if (seg[ind*2].sm<=seg[ind*2+1].sm) { seg[ind].sm=seg[ind*2].sm; seg[ind].pos=seg[ind*2].pos; } else { seg[ind].sm=seg[ind*2+1].sm; seg[ind].pos=seg[ind*2+1].pos; } }*/ 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 main() { cin>>n>>k; if (k!=1) { 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"; } else { for (int q=1;q<=n;q++) cin>>b[q]; for (int q=1;q<=n;q++) b2[q]=b[q]; /*if (b[n]!=-1) { cout<<"-1\n"; return 0; }*/ 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=0; pr1[0]=0; for (int q=1;q<=n;q++) { if (b[q-1]==-1) pr1[q]=q-1; else pr1[q]=pr1[q-1]; } Initialise(1,1,n); for (tm=1;tm<n;tm++) { Push(1,1,n); int sm=seg[1].sm; int pos=seg[1].pos; cout<<tm<<" "<<pos<<" "<<sm<<"\n"; if (sm!=1) break; ansk[pos]=tm; UpdateCh(1,1,n,pos); if (pos!=1) Update(1,1,n,pr1[pos]+1,pos-1); }*/ /*if (tm-1 != br2) { cout<<"-1\n"; return 0; }*/ /*int dok=1; for (int q=1;q<=n;q++) { if (b[q]==1) { ansk[q]=dok; dok++; int cur=b[q]; for (int w=q-1;w>=1;w--) { if (b[w]!=cur+1) break; ansk[w]=dok; dok++; cur++; } } }*/ 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"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:227:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<perm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |         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...