Submission #374922

#TimeUsernameProblemLanguageResultExecution timeMemory
374922maroonrkCounting Mushrooms (IOI20_mushrooms)C++17
100 / 100
13 ms1312 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class t,class u> void print(const pair<t,u>&p,int suc=1){ print(p.a,2); print(p.b,suc); } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } struct sub_solver{ const int nmax; vi dp,pre; vvc<vi> qs; vi flip(int n,vi x){ assert(is_sorted(all(x))); vi y; rep(i,n)if(!binary_search(all(x),i)){ y.pb(i); } return y; } sub_solver(const int nmax_):nmax(nmax_),dp(nmax),pre(nmax,-1),qs(nmax){ dp[1]=1; qs[1].pb(vi{0}); rng(n,2,nmax){ auto check=[&](int m){ return m+dp[m/2]-1>=n; }; int lw=1,up=n; while(up-lw>1){ int mid=(lw+up)/2; if(check(mid))up=mid; else lw=mid; } pre[n]=up; int a=(up+1)/2,b=up/2; dp[n]=dp[a]+dp[b]; int dif=dp[a]-dp[b]; rep(i,dif){ qs[n].pb(qs[a][i]); } rep(i,dp[b]-1){ { vi tmp=flip(a,qs[a][dif+i]); for(auto j:qs[b][i]) tmp.pb(a+j); qs[n].pb(tmp); } { vi tmp=qs[a][dif+i]; for(auto j:qs[b][i]) tmp.pb(a+j); if(up+i<n)tmp.pb(up+i); qs[n].pb(tmp); } } qs[n].pb(qs[a].back()); vi tmp(n);iota(all(tmp),0); qs[n].pb(tmp); assert(si(qs[n])==dp[n]); } } vi restore(int n,vi vs){ assert(dp[n]==si(vs)); if(n==1){ return vs; }else{ int a=(pre[n]+1)/2,b=pre[n]/2; int dif=dp[a]-dp[b]; vi res(n); int w=vs[dp[n]-2]; vi x,y; rep(i,dif){ x.pb(vs[i]); } int tot=0; rep(i,dp[b]-1){ int p=vs[dif+i*2],q=vs[dif+i*2+1]; int z=(p+q)-w; if(a+b+i<n){ res[a+b+i]=z%2; tot+=z%2; } y.pb(z/2); x.pb(w-p+z/2); } x.pb(w); y.pb(vs.back()-w-tot); auto xx=restore(a,x); auto yy=restore(b,y); rep(i,a)res[i]=xx[i]; rep(i,b)res[a+i]=yy[i]; return res; } } template<class F> vi test(int n,F f){ vi y; for(auto x:qs[n]) y.pb(f(x)); return restore(n,y); } }; int count_mushrooms(int n){ vi idx[2]; idx[0].pb(0); int head=1; int off[2]{}; int vmax=150; sub_solver sub(vmax); vmax=lwb(sub.dp,48)-1; while(head<n){ int k=si(idx[0])<si(idx[1]); int len=si(idx[k]); if(inc(2,len,vmax)){ int u=min(n-head,len-1); vi vs; for(auto ls:sub.qs[u]){ int z=-1; if(head+u<n){ z=--n; } vi tmp; if(z!=-1)tmp.pb(z); tmp.pb(idx[k][0]); rep(i,si(ls)){ tmp.pb(head+ls[i]); tmp.pb(idx[k][i+1]); } int val=use_machine(tmp); if(z!=-1){ idx[k^(val%2)].pb(z); } vs.pb(val/2); } vi res=sub.restore(u,vs); rep(i,u)idx[k^res[i]].pb(head+i); head+=u; }else{ vi tmp; rep(i,len){ tmp.pb(idx[k][i]); if(head<n){ tmp.pb(head++); } } int use=si(tmp)-len; int val=use_machine(tmp); int dif=(val+1)/2; off[k^1]+=dif; off[k]+=use-dif; if(use==len){ k^=val%2; off[k]--; idx[k].pb(head-1); } } } return si(idx[0])+off[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...