Submission #1066219

#TimeUsernameProblemLanguageResultExecution timeMemory
1066219Ahmed57Counting Mushrooms (IOI20_mushrooms)C++17
88.63 / 100
6 ms600 KiB
#include "bits/stdc++.h" using namespace std; #include "mushrooms.h" mt19937 rnd; int count_mushrooms(int n){ rnd.seed(time(0)); int mi = 1e9 ; int B = 3; for(int b = 3;b<=n;b++){ int cost = b/2+2; int ma = (b+1)/2; cost+=(n-b+ma-1)/ma; if(cost<mi){ mi = cost; B = b; } } B-=5; B = max(B,3); vector<int> BS[2]; int cnt = 0; vector<int> label; for(int i = 0;i<n;i++)label.push_back(i); shuffle(label.begin()+1,label.end(),rnd); vector<int> pending; BS[0].push_back(0); for(int i = 1;i<min(n,3);i++){ if(use_machine({0,label[i]})){ BS[1].push_back(label[i]); }else { BS[0].push_back(label[i]); } } int la = 2; for(int i = 3;i+1<min(n,B);i+=2){ la = i+1; if(BS[0].size()>1){ //A int an = use_machine({BS[0][0],label[i],BS[0][1],label[i+1]}); if(an==0){ BS[0].push_back(label[i]); BS[0].push_back(label[i+1]); continue; }if(an==1){ BS[0].push_back(label[i]); BS[1].push_back(label[i+1]); continue; }if(an==2){ BS[1].push_back(label[i]); BS[0].push_back(label[i+1]); continue; }else{ BS[1].push_back(label[i]); BS[1].push_back(label[i+1]); continue; } }else{ int an = use_machine({BS[1][0],label[i],BS[1][1],label[i+1]}); if(an==0){ BS[1].push_back(label[i]); BS[1].push_back(label[i+1]); continue; }if(an==1){ BS[1].push_back(label[i]); BS[0].push_back(label[i+1]); continue; }if(an==2){ BS[0].push_back(label[i]); BS[1].push_back(label[i+1]); continue; }else{ BS[0].push_back(label[i]); BS[0].push_back(label[i+1]); continue; } } } if(la+1<min(n,B)){ if(use_machine({0,label[la+1]})){ BS[1].push_back(label[la+1]); }else BS[0].push_back(label[la+1]); } cnt = BS[0].size(); int sz = max(BS[0].size(),BS[1].size()); vector<int> bs; for(int i = B;i<n;i+=sz){ sz = max(sz,(int)max(BS[0].size(),BS[1].size())); int As , typ; if(BS[0].size()>BS[1].size()){ As = 1;typ = 0; }else As = 0 , typ = 1; int xd = i; vector<int> lol; int nah = 0; int last = -1; for(int j = i;j<min(n,i+sz);j++){ nah++; lol.push_back(BS[typ][j-i]); lol.push_back(label[j]); last = label[j]; } int ans = use_machine(lol); if(ans%2){ if(As==0){ cnt++; BS[0].push_back(last); }else BS[1].push_back(last); ans--; }else{ if(As==1){ cnt++; BS[0].push_back(last); }else BS[1].push_back(last); } ans/=2; nah--; if(As==0)cnt+=ans; else cnt+=nah-ans; } return cnt; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:93:13: warning: unused variable 'xd' [-Wunused-variable]
   93 |         int xd = i;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...