Submission #308525

#TimeUsernameProblemLanguageResultExecution timeMemory
308525PetiCounting Mushrooms (IOI20_mushrooms)C++14
87.26 / 100
10 ms384 KiB
#include "mushrooms.h" #include <iostream> #include <utility> #include <vector> using namespace std; const int find_first = 125; pair<int, int> ask_querry(vector<int> &inds, int &x, int &n){ int m = min((int)inds.size()*2, (n-x)*2); m = min(m, n - n%2); vector<int> querry(m); for(int i = 0; i < m; i += 2) querry[i] = inds[i/2]; for(int i = 1; i < m; i += 2) querry[i] = x++; return make_pair(use_machine(querry), m); } int count_mushrooms(int n) { int ret = 1, x = 1; vector<int> indsA, indsB; indsA.push_back(0); while((int)indsA.size() < 2 && (int)indsB.size() < 2) { if(x == n) return ret; vector<int> querry = {0, x}; int ans = use_machine(querry); if(ans == 0) { indsA.push_back(x); ret++; } else indsB.push_back(x); x++; } while((int)indsA.size() < find_first && (int)indsB.size() < find_first) { if(x == n) return ret; if(x == n-1) { vector<int> querry = {0, x}; int ans = use_machine(querry); if(ans == 0) return ret + 1; return ret; } vector<int> querry(4); if((int)indsA.size() > 1) { querry[0] = indsA[0]; querry[2] = indsA[1]; querry[1] = x; querry[3] = x+1; int ans = use_machine(querry); ret += 2 - (ans+1)/2; if(ans < 2) indsA.push_back(x); else indsB.push_back(x); if(ans%2 == 0) indsA.push_back(x+1); else indsB.push_back(x+1); x += 2; } else { querry[0] = indsB[0]; querry[2] = indsB[1]; querry[1] = x; querry[3] = x+1; int ans = use_machine(querry); ret += (ans+1)/2; if(ans >= 2) indsA.push_back(x); else indsB.push_back(x); if(ans%2 == 1) indsA.push_back(x+1); else indsB.push_back(x+1); x += 2; } } while(x < n) { if(indsA.size() > indsB.size()) { pair<int, int> ans = ask_querry(indsA, x, n); if(ans.first%2 == 0) indsA.push_back(x-1); ret += ans.second/2 - (ans.first+1)/2; } else { pair<int, int> ans = ask_querry(indsB, x, n); if(ans.first%2 == 1) indsA.push_back(x-1); ret += (ans.first+1)/2; } } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...