Submission #1228311

#TimeUsernameProblemLanguageResultExecution timeMemory
1228311vivkostovLibrary (JOI18_library)C++20
19 / 100
82 ms460 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; int n; vector<int>otg; struct cell { int st,l,r; }; int islead[10005],p[40005],used[10005]; cell a[10005]; vector<int>v; int get(int l,int r,int ad) { for(int i=l;i<=r;i++) { v[i-1]=1; } if(ad)v[ad-1]=1; int q=Query(v); for(int i=1;i<=n;i++) { v[i-1]=0; } return q; } void prec() { for(int i=1;i<=n;i++) { islead[i]=1; a[i].st=i; a[i].l=0; a[i].r=0; v.push_back(0); } } void merg(int i,int j) { if(a[i].r==0)a[i].r=j; else a[i].l=j; if(a[j].r==0)a[j].r=i; else a[j].l=i; if(a[i].l!=0&&a[i].r!=0)islead[i]=0; if(a[j].l!=0&&a[j].r!=0)islead[j]=0; } int bin(int l,int r,int i) { int L=l,R=r,m,h1,h2=0; while(L<=R) { m=(L+R)/2; h1=get(L,m,0); if(n<=200)h2=get(L,m,i); if(h1>=h2&&n<=200)R=m-1; else L=m+1; } if(n<=200)return L; else return l; } void fix(int l,int r,int h) { int mid=(l+r)/2,w,g; for(int i=mid+1;i<=r;i++) { if(!islead[i])continue; w=get(l,mid,i); if(w==p[h*2]+1)continue; g=bin(l,r,i); //cout<<g<<" "<<i<<endl; merg(g,i); if(w==p[h*2])continue; g=bin(g+1,mid,i); //cout<<g<<" "<<i<<endl; merg(g,i); } } void build(int l,int r,int h) { if(l==r) { p[h]=1; return; } int mid=(l+r)/2; build(l,mid,h*2); build(mid+1,r,h*2+1); p[h]=get(l,r,0); if(p[h]!=p[h*2]+p[h*2+1]) { fix(l,r,h); } } void Solve(int N) { n=N; prec(); build(1,n,1); int lead=1; for(int i=1;i<=n;i++) { if(islead[i]) { lead=i; break; } } if(n>200) { for(int i=1;i<=n;i++)otg.push_back(i); Answer(otg); return; } /*cout<<endl<<endl; for(int i=1;i<=n;i++) { cout<<a[i].l<<" "<<a[i].r<<endl; } cout<<endl;*/ used[0]=1; while(true) { used[lead]=1; otg.push_back(lead); if(!used[a[lead].l])lead=a[lead].l; else if(!used[a[lead].r])lead=a[lead].r; else break; } //for(int i=1;i<=n;i++)otg.push_back(i); Answer(otg); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...