Submission #307807

#TimeUsernameProblemLanguageResultExecution timeMemory
307807CodePlatinaCounting Mushrooms (IOI20_mushrooms)C++14
69.54 / 100
14 ms512 KiB
#include "mushrooms.h" #include <vector> using namespace std; int count_mushrooms(int n) { if(n <= 452) { int ret = 1; for(int i = 1; i < n; i += 2) { if(i == n - 1) ret += 1 - use_machine({0, i}); else ret += 2 - use_machine({i, 0, i + 1}); } return ret; } else { int ret = 1; vector<int> A, B, C; A.push_back(0); for(int i = 1; i < n; ++i) C.push_back(i); while(A.size() < 116 && B.size() < 116) { if(B.empty() || B.size() > A.size()) { int x = C.back(); C.pop_back(); int y = C.back(); C.pop_back(); int t = use_machine({A[0], x, y}); if(t == 0) { A.push_back(x); A.push_back(y); ret += 2; } else if(t == 1) { B.push_back(y); C.push_back(x); } else if(t == 2) { A.push_back(y); B.push_back(x); ret += 1; } } else { int x = C.back(); C.pop_back(); int y = C.back(); C.pop_back(); int t = use_machine({B[0], x, y}); if(t == 0) { B.push_back(x); B.push_back(y); } else if(t == 1) { A.push_back(y); C.push_back(x); ret += 1; } else if(t == 2) { A.push_back(x); B.push_back(y); ret += 1; } } } if(A.size() >= B.size()) { for(int i = 0; i < (int)C.size(); i += (int)A.size()) { int cnt = 0; vector<int> tmp; for(int j = i; j < (int)C.size() && j < i + (int)A.size(); ++j) { ++cnt; tmp.push_back(A[j - i]); tmp.push_back(C[j]); } int t = use_machine(tmp); if(t & 1) ++t; t /= 2; ret += cnt - t; } } else { swap(A, B); for(int i = 0; i < (int)C.size(); i += (int)A.size()) { int cnt = 0; vector<int> tmp; for(int j = i; j < (int)C.size() && j < i + (int)A.size(); ++j) { ++cnt; tmp.push_back(A[j - i]); tmp.push_back(C[j]); } int t = use_machine(tmp); if(t & 1) ++t; t /= 2; ret += t; } } return ret; } }
#Verdict Execution timeMemoryGrader output
Fetching results...