Submission #1046596

#TimeUsernameProblemLanguageResultExecution timeMemory
1046596MarwenElarbiCounting Mushrooms (IOI20_mushrooms)C++17
56.64 / 100
6 ms628 KiB
#include <bits/stdc++.h> using namespace std; #include "mushrooms.h" #define pb push_back mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int count_mushrooms(int n) { int a=1; int b=0; vector<int> aa; aa.pb(0); vector<int> bb; int lst=1; vector<int> per; for (int i = 0; i < n; ++i) { per.pb(i); } shuffle(per.begin()+1,per.end(),rng); for (int i = 1; i < min(n,200); i++) { if(aa.size()==100||bb.size()==100) break; lst=i+1; int cur=use_machine({per[i],0}); (cur==1 ? bb : aa).pb(per[i]); (cur==1 ? b : a)++; } int ans=a; for (int i = lst; i < n; i+=99) { vector<int> cur; int k=0; cur.pb((aa.size()>bb.size() ? aa[k++] : bb[k++])); for (int j = 0; j < min(n-i,99); ++j) { cur.pb(per[j+i]); cur.pb((aa.size()>bb.size() ? aa[k++] : bb[k++])); } int cnt=use_machine(cur); ans+=(aa.size()<=bb.size() ? cnt/2 : cur.size()-k-cnt/2); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...