Submission #221563

#TimeUsernameProblemLanguageResultExecution timeMemory
221563dorijanlendvajLibrary (JOI18_library)C++14
0 / 100
482 ms3204 KiB
#include "library.h" #include <bits/stdc++.h> #define x first #define y second #define pii pair<int,int> #define pb push_back #define eb emplace_back #pragma GCC optimize("unroll-loops") #define vi vector<int> #define vl vector<ll> #define all(a) begin(a),end(a) using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; int n,col[1010],par[1010]; vi sa[1010]; vi ch[1010]; map<pii,int> ma; vi sol; void merge(int a,int b) { ch[a].pb(b); ch[b].pb(a); bool cha=col[a]==col[b]; a=par[a]; b=par[b]; for (auto x: sa[b]) { sa[a].pb(x); par[x]=a; if (cha) col[x]^=1; } } void dfs(int i,int p=-1) { sol.pb(i+1); for (auto a: ch[i]) if (a!=p) dfs(a,i); } int f(int l,int r) { if (r<=l) return r-l+1; if (ma.find({l,r})!=ma.end()) return ma[{l,r}]; vi v; for (int j=0;j<l;++j) v.pb(0); for (int j=l;j<=r;++j) v.pb(1); for (int j=r+1;j<n;++j) v.pb(0); return ma[{l,r}]=Query(v); } void Solve(int N) { n=N; for (int i=0;i<n;++i) par[i]=i,col[i]=0,sa[i]={i}; int la=0; while (la<n-1) { int c=f(0,la)-la; while (f(0,la)-la==c) ++la; int dif=c-(f(0,la)-la); int lo=-1,hi=la-1; while (lo<hi) { int mid=(lo+hi+1)/2; vi v(n); int cn=0; for (int i=mid;i<la;++i) if (col[i]==0) v[i]=1,++cn; v[la]=1,++cn; if (Query(v)==cn) { cn=0; v=vi(n,0); for (int i=mid;i<la;++i) if (col[i]==1) v[i]=1,++cn; v[la]=1,++cn; if (Query(v)==cn) hi=mid-1; else lo=mid; } else lo=mid; } merge(la,lo); if (dif==2) { int pre=lo; lo=-1,hi=la-1; while (lo<hi) { int mid=(lo+hi+1)/2; vi v(n); int cn=0; for (int i=mid;i<la;++i) if (col[i]==0 && i!=pre) v[i]=1,++cn; v[la]=1,++cn; if (Query(v)==cn) { cn=0; v=vi(n,0); for (int i=mid;i<la;++i) if (col[i]==1 && i!=pre) v[i]=1,++cn; v[la]=1,++cn; if (Query(v)==cn) hi=mid-1; else lo=mid; } else lo=mid; } merge(la,lo); } } for (int i=0;i<n;++i) if (ch[i].size()==1) { dfs(i); break; } Answer(sol); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...