Submission #911450

#TimeUsernameProblemLanguageResultExecution timeMemory
911450biankMechanical Doll (IOI18_doll)C++14
84 / 100
148 ms16548 KiB
#include <bits/stdc++.h> #include "doll.h" using namespace std; #define SIZE(x) (int)x.size() #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define pb push_back typedef vector<int> vi; vi L, R, v, state; int t=1, skip, s=0; void build(int u, int l, int r) { //[l,r] L.pb(0), R.pb(0), v.pb(1); if(l>r) return; if(skip>0 && r-l+1<=skip) { assert(u>=0); assert(u<SIZE(v)); v[u]=-1; skip-=r-l+1; return; } if(l==r) { assert(u>=0); assert(u<SIZE(v)); v[u]=0; return; } v[u]=--s; int m=(l+r)/2; assert(u>=0); assert(u<SIZE(L)); L[u] = t++; build(L[u], l, m); assert(u>=0); assert(u<SIZE(R)); R[u] = t++; build(R[u], m+1, r); //dbgm(u,l,r,v[u],L[u],R[u]); } bool dfs(int u, int a) { //dbg(u); assert(u>=0); assert(u<SIZE(v)); if(u!=0 && v[u]==-1) return false; if(!v[u]) { //dbgm(u,v[u]); v[u]=a; return true; } assert(u<SIZE(state)); state[u]^=1; assert(u<SIZE(L)); assert(u<SIZE(R)); assert(v[L[u]]!=-1 || v[R[u]]!=-1); if(state[u]) return dfs(L[u],a); return dfs(R[u],a); } void create_circuit(int m, vi A) { vi c(m+1); assert(0<SIZE(c)); assert(0<SIZE(A)); c[0]=A[0]; forsn(i,1,m+1) { assert(i>=0); assert(i<SIZE(c)); c[i]=-1; } int n=SIZE(A); int sz=1; while(sz<n) sz*=2; assert(sz>=n); skip = sz-n; build(0,1,sz); assert(SIZE(L)==SIZE(R)); assert(SIZE(v)==SIZE(L)); //dbgm(L,R,v); vi a; forsn(i,1,n) { assert(i>=0); assert(i<SIZE(A)); a.pb(A[i]); } a.pb(0); assert(SIZE(a)==n); state.assign(SIZE(v),0); forn(i,n) { assert(i<SIZE(a)); bool flag=0; while(!flag) flag=dfs(0,a[i]); } vi x, y; forn(i,SIZE(v)) { assert(i<SIZE(L)); assert(i<SIZE(R)); if(L[i] && R[i]) { x.pb(v[L[i]]); y.pb(v[R[i]]); } } answer(c,x,y); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...