Submission #306915

#TimeUsernameProblemLanguageResultExecution timeMemory
306915baluteshihCounting Mushrooms (IOI20_mushrooms)C++14
92.62 / 100
13 ms512 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=75; int count_mushrooms(int n) { if(n==2) return 2-use_machine({0,1}); srand(time(NULL)); int ans=0; 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]); for(int i=2,j=0;i+1<SZ(num)&&j<K;i+=2,++j) { if(SZ(a)>=2) { int x=use_machine({a[0],num[i],a[1],num[i+1]}); if(x==0) a.pb(num[i]),a.pb(num[i+1]); else if(x==1) a.pb(num[i]),b.pb(num[i+1]); else if(x==2) a.pb(num[i+1]),b.pb(num[i]); else b.pb(num[i]),b.pb(num[i+1]); } else { int x=use_machine({b[0],num[i],b[1],num[i+1]}); if(x==0) b.pb(num[i]),b.pb(num[i+1]); else if(x==1) b.pb(num[i]),a.pb(num[i+1]); else if(x==2) b.pb(num[i+1]),a.pb(num[i]); else a.pb(num[i]),a.pb(num[i+1]); } } if(SZ(num)<=2+2*K) { if((n&1)^1) { if(use_machine({0,num.back()})==0) a.pb(num.back()); else b.pb(num.back()); } return SZ(a); } ans=SZ(a); int nw=2+2*K; 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...