Submission #344078

#TimeUsernameProblemLanguageResultExecution timeMemory
344078KerimLibrary (JOI18_library)C++17
0 / 100
236 ms262148 KiB
#include <cstdio> #include <vector> #include "library.h" #define pb(x) push_back(x) #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define N 1003 using namespace std; int val[N],n; vector<int>adj[N],res; void add(int x,int y){ //printf("%d %d\n",x,y); adj[x].pb(y); adj[y].pb(x); } void dfs(int nd,int pr){ res.pb(nd); tr(it,adj[nd]) if(*it!=pr) dfs(*it,nd); } int ask(int x,int i,int effect){ vector<int>M; int cur=0; for(int j=0;j<n;j++){ if(j>=x and j<=i) cur+=val[j],M.pb(1); else M.pb(0); } //printf("ask %d %d %d %d %d\n",x,i,effect,(Query(M)+cur<=i-x-effect),cur); return (Query(M)+cur<=i-x-effect); } void Solve(int nn){n=nn; if(n==1){ res.pb(1); Answer(res); return; } for(int i=1;i<n;i++){ int st=0,en=i-1,a=-1,b=-1; while(st<en){ int mid=(st+en+1)>>1; if(ask(mid,i,0)) st=mid; else en=mid-1; } if(ask(st,i,0)){ add(st+1,i+1);a=st; en=st-1;st=0; if(st<=en){ //printf("%d %d %d\n",st,en,i); while(st+1<en){ int mid=(st+en+1)>>1; if(ask(mid,i,1)) st=mid; else en=mid-1; } if(ask(st,i,1)) add(st+1,i+1),b=st; } } if(~a)val[a]++; if(~b)val[b]++; } for(int i=1;i<=n;i++) if(adj[i].size()==1){ dfs(i,-1); break; } Answer(res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...