Submission #831235

#TimeUsernameProblemLanguageResultExecution timeMemory
831235BaytoroCounting Mushrooms (IOI20_mushrooms)C++17
92.62 / 100
8 ms336 KiB
#include "mushrooms.h" //#include "stub.cpp" #include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second #define all(x) x.begin(),x.end(); int count_mushrooms(int n) { vector<int> a[2]; a[0].pb(0); int last=1; for(int i=1;i<n && max(a[0].size(),a[1].size())<2;i++){ if(use_machine({0,i})) a[1].pb(i); else a[0].pb(i); last++; } for(int i=last;i+1<n && (int)a[0].size()<80 && (int)a[1].size()<80;){ int x=0; if(a[0].size()<2) x=1; int cnt=use_machine({a[x][0],i,a[x][1],i+1}); if(cnt==0) {a[x].pb(i);a[x].pb(i+1);} if(cnt==1) {a[x].pb(i);a[x^1].pb(i+1);} if(cnt==2) {a[x].pb(i+1);a[x^1].pb(i);} if(cnt==3) {a[x^1].pb(i);a[x^1].pb(i+1);} i+=2; last=i; } vector<int> A(2); A[0]=a[0].size(); A[1]=a[1].size(); for(int i=last;i<n;){ int x=0,s=a[0].size(); if(s<(int)a[1].size()) x=1,s=a[1].size(); int l=min(i+s,n); vector<int> v; for(int j=i;j<l;j++){ v.pb(a[x][j-i]); v.pb(j); } int cnt=use_machine(v); if(cnt%2) A[x^1]++,a[x^1].pb(l-1),cnt--; else A[x]++,a[x].pb(l-1); A[x^1]+=(cnt+1)/2,A[x]+=(l-i-1-(cnt+1)/2); i=l; } return A[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...