Submission #306964

#TimeUsernameProblemLanguageResultExecution timeMemory
306964baluteshihCounting Mushrooms (IOI20_mushrooms)C++14
99.12 / 100
10 ms580 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define X first #define Y second #define ALL(v) v.begin(),v.end() #define pb push_back #define SZ(a) ((int)a.size()) const int K=70; int count_mushrooms(int n) { int ans=0; if(n<=227) { ++ans; for(int i=1;i<n;++i) ans+=(use_machine({0,i})==0); return ans; } srand(time(NULL)); vector<int> num(n-1,0); vector<int> a(1,0),b; for(int i=0;i+1<n;++i) num[i]=i+1; random_shuffle(ALL(num)); for(int i=0;i<2;++i) if(use_machine({0,num[i]})==0) a.pb(num[i]); else b.pb(num[i]); if(SZ(a)>SZ(b)) { int x=use_machine({a[0],num[2],a[1],num[3]}); if(x==0) a.pb(num[2]),a.pb(num[3]); else if(x==1) a.pb(num[2]),b.pb(num[3]); else if(x==2) a.pb(num[3]),b.pb(num[2]); else b.pb(num[2]),b.pb(num[3]); } else { int x=use_machine({b[0],num[2],b[1],num[3]}); if(x==0) b.pb(num[2]),b.pb(num[3]); else if(x==1) b.pb(num[2]),a.pb(num[3]); else if(x==2) b.pb(num[3]),a.pb(num[2]); else a.pb(num[2]),a.pb(num[3]); } vector<int> tmp; for(int i=4,j=0;i+2<SZ(num)&&j<K;++j) { int x; if(SZ(a)>=3) { if(!tmp.empty()) { x=use_machine({a[0],tmp.back(),a[1],num[i],a[2],num[i+1]}); if(x&1) b.pb(num[i+1]); else a.pb(num[i+1]); if(x<=1||x>=4) { for(int nw=(x>=4);!tmp.empty();nw^=1,tmp.pop_back()) if(nw==0) a.pb(tmp.back()); else b.pb(tmp.back()); if(x<=1) a.pb(num[i]); else b.pb(num[i]); } else tmp.pb(num[i]); i+=2; } else { x=use_machine({a[0],num[i],a[1],num[i+1],a[2],num[i+2]}); if(x&1) b.pb(num[i+2]); else a.pb(num[i+2]); if(x<=1) a.pb(num[i]),a.pb(num[i+1]); else if(x>=4) b.pb(num[i]),b.pb(num[i+1]); else tmp.pb(num[i]),tmp.pb(num[i+1]); i+=3; } } else { if(!tmp.empty()) { x=use_machine({b[0],tmp.back(),b[1],num[i],b[2],num[i+1]}); if(x&1) a.pb(num[i+1]); else b.pb(num[i+1]); if(x<=1||x>=4) { for(int nw=(x>=4);!tmp.empty();nw^=1,tmp.pop_back()) if(nw==0) b.pb(tmp.back()); else a.pb(tmp.back()); if(x<=1) b.pb(num[i]); else a.pb(num[i]); } else tmp.pb(num[i]); i+=2; } else { x=use_machine({b[0],num[i],b[1],num[i+1],b[2],num[i+2]}); if(x&1) a.pb(num[i+2]); else b.pb(num[i+2]); if(x<=1) b.pb(num[i]),b.pb(num[i+1]); else if(x>=4) a.pb(num[i]),a.pb(num[i+1]); else tmp.pb(num[i]),tmp.pb(num[i+1]); i+=3; } } } if(!tmp.empty()) { for(int nw=use_machine({0,tmp.back()});!tmp.empty();nw^=1,tmp.pop_back()) if(nw==0) a.pb(tmp.back()); else b.pb(tmp.back()); } ans=SZ(a); int nw=SZ(a)+SZ(b)-1; while(nw+max(SZ(a),SZ(b))<=SZ(num)) { if(SZ(a)>=SZ(b)) { int q=SZ(a); vector<int> tmp; for(int j=0;j<q;++j) tmp.pb(a[j]),tmp.pb(num[nw+j]); int x=use_machine(tmp); if(x&1) --x,b.pb(num[nw+q-1]); else ++ans,a.pb(num[nw+q-1]); ans+=((q-1)*2-x)/2; nw+=q; } else { int q=SZ(b); vector<int> tmp; for(int j=0;j<q;++j) tmp.pb(b[j]),tmp.pb(num[nw+j]); int x=use_machine(tmp); if(x&1) ++ans,--x,a.pb(num[nw+q-1]); else b.pb(num[nw+q-1]); ans+=x/2; nw+=q; } } if(nw<SZ(num)) { if(SZ(a)>=SZ(b)) { vector<int> tmp; for(int j=0;nw+j<SZ(num);++j) tmp.pb(a[j]),tmp.pb(num[nw+j]); tmp.pb(a.back()); int x=use_machine(tmp); ans+=((SZ(num)-nw)*2-x)/2; } else { vector<int> tmp; for(int j=0;nw+j<SZ(num);++j) tmp.pb(b[j]),tmp.pb(num[nw+j]); tmp.pb(b.back()); int x=use_machine(tmp); ans+=x/2; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...