Submission #305078

#TimeUsernameProblemLanguageResultExecution timeMemory
305078MarcoMeijerCounting Mushrooms (IOI20_mushrooms)C++14
100 / 100
9 ms384 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() int mx=195; int count_mushrooms(int n) { if(n <= 227) { int ans = 1; REP(i,1,n) ans += 1-use_machine({0,i}); return ans; } int cur = 0; vi a[2]; bool swp = 0; a[0].pb(cur++); // A_ while(a[0].size() < 2 && a[1].size() < 2) { a[use_machine({a[0][0], cur})].pb(cur); cur++; } if(a[1].size() > a[0].size()) swap(a[0],a[1]), swp^=1; // A_A_ while(a[0].size() < 3 && a[1].size() < 3) { vi m; m.pb(a[0][0]); m.pb(cur); m.pb(a[0][1]); m.pb(cur+1); int res = use_machine(m); a[(res&2)==2].pb(cur); a[(res&1)==1].pb(cur+1); cur += 2; } if(a[1].size() > a[0].size()) swap(a[0],a[1]), swp^=1; // A_A_A_ => A_A_ while(cur < mx && a[1].size() < 2) { vi m; m.pb(a[0][0]); m.pb(cur); m.pb(a[0][1]); m.pb(cur+1); m.pb(a[0][2]); m.pb(cur+2); int res = use_machine(m); a[(res&1)==1].pb(cur+2); if(res&2) { m.clear(); m.pb(a[0][0]); m.pb(cur); m.pb(a[0][1]); m.pb(cur+1); res = use_machine(m); a[(res&2)==2].pb(cur); a[(res&1)==1].pb(cur+1); } else { a[(res&4)==4].pb(cur ); a[(res&4)==4].pb(cur+1); } cur += 3; if(a[1].size() > a[0].size()) swap(a[0],a[1]), swp^=1; } // A_A_A_ => B_BA_A_A_ while(cur < mx) { vi m; m.pb(a[0][0]); m.pb(cur); m.pb(a[0][1]); m.pb(cur+1); m.pb(a[0][2]); m.pb(cur+2); int res = use_machine(m); a[(res&1)==1].pb(cur+2); if(res&2) { m.clear(); m.pb(a[1][0]); m.pb(cur); m.pb(a[1][1]); m.pb(a[0][0]); m.pb(cur+1); m.pb(a[0][1]); m.pb(cur+3); m.pb(a[0][2]); m.pb(cur+4); res = use_machine(m)-1; a[(res&2)==2].pb(cur+3); a[(res&1)==1].pb(cur+4); if(res&4) { a[0].pb(cur); a[1].pb(cur+1); } else { a[1].pb(cur); a[0].pb(cur+1); } cur += 5; } else { a[(res&4)==4].pb(cur+1); a[(res&4)==4].pb(cur ); cur += 3; } } if(a[1].size() > a[0].size()) swap(a[0],a[1]), swp^=1; int ans = a[swp].size(); while(cur < n) { vi m; FOR(i,a[0]) { m.pb(i); m.pb(cur++); if(cur == n) break; } int res = use_machine(m); if(swp) ans += (res+1)/2; else ans += m.size()/2 - (res+1)/2; a[(res&1)==1].pb(cur-1); if(a[1].size() > a[0].size()) swap(a[0],a[1]), swp^=1; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...