Submission #1228152

#TimeUsernameProblemLanguageResultExecution timeMemory
1228152NonozeCounting Mushrooms (IOI20_mushrooms)C++20
25 / 100
5 ms420 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define cmin(a, b) a=min(a, b) #define cmax(a, b) a=max(a, b) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)x.size() using namespace std; int n; vector<int> A(1, 0), B; int calcone(int &i) { // cout << "OK" << endl; auto val=2-use_machine({i, A[0], i+1}); if (val==2) A.pb(i), A.pb(i+1); else if (val==0) B.pb(i), B.pb(i+1); else { if (!use_machine({A[0], i})) A.pb(i), B.pb(i+1); else A.pb(i+1), B.pb(i); } i+=2; return val; } int calcA(int &i, bool create=1) { int l=i, r=min(n-1, i+sz(A)-2); vector<int> m; for (auto &u: A) { if (i>=n) break; m.pb(u), m.pb(i++); } m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--; i++; auto val=sz(m)/2 - use_machine(m)/2; if (create) { int cnt=0; for (; l<r && cnt<val; l++) { if (!use_machine({A[0], l})) A.pb(l), cnt++; else B.pb(l); } if (cnt<val) A.pb(l); else B.pb(l); } return val; } int calcB(int &i, bool create=1) { int l=i, r=min(n-1, i+sz(B)-2); vector<int> m; for (auto &u: B) { m.pb(u), m.pb(i++); } m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--; i++; auto val=use_machine(m)/2; if (create) { int cnt=0; for (; l<r && cnt<val; l++) { if (!use_machine({A[0], l})) A.pb(l), cnt++; else B.pb(l); } if (cnt<val) A.pb(l); else B.pb(l); } return val; } int count_mushrooms(int _n) { n=_n; int ans=1; for (int i=1; i<n;) { // cout << i << ' '; if (i==n-1) { ans+=1-use_machine({0, i}); i++; } else { if (sz(A)>sz(B) || sz(B)<3) { if (sz(A)<=2) ans+=calcone(i); else ans+=calcA(i, sz(A)<20); } else { ans+=calcB(i, sz(B)<20); } } // cout << i-1 << ' ' << ans << endl; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...