Submission #1052279

#TimeUsernameProblemLanguageResultExecution timeMemory
1052279fuad27Counting Mushrooms (IOI20_mushrooms)C++17
0 / 100
1 ms344 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; int count_mushrooms(int n) { if(n == 2) { return 2-use_machine({0, 1}); } int bb = min(282, n); int ss = use_machine({0, 1}); int tt = use_machine({0, 2}); vector<int> A, B; A.push_back(0); if(ss==0) A.push_back(1); else B.push_back(1); if(tt==0) A.push_back(2); else B.push_back(2); for(int i = 3;i<bb;i+=2) { if(i + 1 < bb) { if(A.size() >= 2) { int val = use_machine(vector{A[0], i, A[1], i+1}); if(val < 2) { A.push_back(i); } else B.push_back(i); if(val%2 == 0) { A.push_back(i+1); } else B.push_back(i+1); } else { int val = use_machine(vector{B[0], i, B[1], i+1}); if(val < 2) { B.push_back(i); } else A.push_back(i); if(val%2 == 0) { B.push_back(i+1); } else A.push_back(i+1); } } else { int val = use_machine(vector{A[0], i}); if(val==0) { A.push_back(i); } else B.push_back(i); } } bool col=0; int szmx=A.size()-1; int ans=A.size(); if(A.size() < B.size()){ col=1; szmx = B.size()-1; ans=B.size(); } for(int i = bb;i<n;i+=szmx) { vector<int> cur; if(col==0)cur.push_back(A[0]); else cur.push_back(B[0]); for(int j = 0;j<min(szmx, n-i);j++) { cur.push_back(i+j); if(col==0)cur.push_back(A[j+1]); else cur.push_back(B[j+1]); } int val = use_machine(cur); ans+=val/2; } if(col)ans=n-ans; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...