Submission #1240341

#TimeUsernameProblemLanguageResultExecution timeMemory
1240341Muhammad_AneeqCounting Mushrooms (IOI20_mushrooms)C++20
56.93 / 100
3 ms452 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; int const mx=100; int count_mushrooms(int n) { if (n<=226) { int ans=0; for (int i=1;i<n;i++) ans+=(use_machine({0,i})); return n-ans; } mt19937 mt(784753459); vector<int>ind[2]={}; ind[0].push_back(0); bool vis[n]={}; vis[0]=1; while (max(ind[0].size(),ind[1].size())<mx) { int z=mt()%n; while (vis[z]) z=mt()%n; vis[z]=1; ind[use_machine({0,z})].push_back(z); } vector<int>lef; bool w=0; if (ind[0].size()<ind[1].size()) { swap(ind[0],ind[1]); w=1; } int cnt[2]={}; for (auto i:{0,1}) cnt[i]=ind[i].size(); for (int i=0;i<n;i++) { if (vis[i]) continue; lef.push_back(i); if (lef.size()==mx) { vector<int>cur; for (int i=0;i<mx;i++) { cur.push_back(lef[i]); cur.push_back(ind[0][i]); } lef={}; int g=use_machine(cur); int cn=(g+1)/2; cnt[1]+=cn; cnt[0]+=mx-cn; } } if (lef.size()) { int sz=lef.size(); vector<int>cur; for (int i=0;i<sz;i++) { cur.push_back(lef[i]); cur.push_back(ind[0][i]); } lef={}; int g=use_machine(cur); int cn=(g+1)/2; cnt[1]+=cn; cnt[0]+=sz-cn; } return cnt[w]; }
#Verdict Execution timeMemoryGrader output
Fetching results...