Submission #1248069

#TimeUsernameProblemLanguageResultExecution timeMemory
1248069nikulidCounting Mushrooms (IOI20_mushrooms)C++20
0 / 100
0 ms428 KiB
#include <iostream> #include "mushrooms.h" using namespace std; bool debug=0; #define dout if(debug)cout #define pb push_back #define mp make_pair int count_mushrooms(int n) { vector<int> m = {0}; if(n<200){ int smallans=1; for(int i=1; i<n; i++){ m = {0, i}; smallans += (1-use_machine(m)); } return smallans; } int answer; int cnt0=1, cnt1=0; vector<int> ones, zeros={0}; vector<bool> known(n+1, 0); known[0]=1; int val; pair<int, int> zs; // spend 2 queries finding atleast a 2nd instance of 1, or 2 instances of 0: known[1]=1; bool usingzeros; m={0,1}; if(use_machine(m)){ // {0,1} cnt1++; ones.pb(1); known[2]=1; m={0,2}; if(use_machine(m)){ // {0,1,1} cnt1++; ones.pb(2); zs = mp(1,2); usingzeros = false; } else{ // {0,1,0} cnt0++; zeros.pb(2); zs = mp(0,2); usingzeros = true; } } else{ cnt0++; zeros.pb(1); zs = mp(0,1); usingzeros = true; } // querying {1,x,1,y} tells us all about x and y. // doing this 100 times is pretty nice dout<<"finished the first 2 queries. we have the pair ("<<zs.first<<","<<zs.second<<").\n"; int a=1,b=1; for(int j=0; j<min(100, n/3); j++){ while(known[a]) a++; known[a]=1; while(known[b]) b++; known[b]=1; m={zs.first, a, zs.second, b}; val = use_machine(m); if(val==0){ // ns[a]=ns[b]=zs if(usingzeros){ cnt0+=2; zeros.pb(a); zeros.pb(b); } else{ cnt1+=2; ones.pb(a); ones.pb(b); } } else if(val==1){ cnt0++; cnt1++; if(usingzeros){ ones.pb(a); zeros.pb(b); } else{ ones.pb(b); zeros.pb(a); } } else if(val==2){ // a is the same as usingzeros cnt0++; cnt1++; if(usingzeros){ zeros.pb(a); ones.pb(b); } else{ ones.pb(a); zeros.pb(b); } } else{ // a==b==!zs if(usingzeros){ cnt1+=2; ones.pb(a); ones.pb(b); } else{ cnt0+=2; zeros.pb(a); zeros.pb(b); } } } if(debug) { cout<<"$ known: "; for(int i=0; i<n; i++){ cout<<known[i]<<" "; }cout<<"\n"; } int next_unknown = 1; while(known[next_unknown])next_unknown++; if(cnt0 >= cnt1){ answer = n-cnt1; while(next_unknown < n){ m = {zeros[0]}; for(int i=1; i<cnt0; i++){ if(next_unknown >= n)break; m.pb(next_unknown); m.pb(zeros[i]); known[next_unknown]=true; while(known[next_unknown])next_unknown++; } answer -= use_machine(m)/2; } return answer; } else{ answer = cnt0; while(next_unknown < n){ m = {ones[0]}; for(int i=1; i<cnt1; i++){ if(next_unknown >= n)break; m.pb(next_unknown); m.pb(ones[i]); known[next_unknown]=true; while(known[next_unknown])next_unknown++; } answer += use_machine(m)/2; } return answer; } }
#Verdict Execution timeMemoryGrader output
Fetching results...