Submission #605065

#TimeUsernameProblemLanguageResultExecution timeMemory
605065SamAndCounting Mushrooms (IOI20_mushrooms)C++17
92.24 / 100
12 ms464 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define m_p make_pair typedef long long ll; mt19937 rnf(234); const int M = 160; int count_mushrooms(int n) { vector<int> v; for (int i = 1; i < min(n, M); ++i) v.push_back(i); vector<int> a; vector<int> b; a.push_back(0); while (!v.empty()) { if (sz(v) == 1 || (max(sz(a), sz(b)) < 2)) { int q = use_machine({0, v.back()}); if (q == 0) a.push_back(v.back()); else b.push_back(v.back()); v.pop_back(); continue; } if (sz(a) >= 2) { int q = use_machine({a[0], v[0], a[1], v[1]}); if (q == 0) { a.push_back(v[0]); a.push_back(v[1]); } else if (q == 3) { b.push_back(v[0]); b.push_back(v[1]); } else if (q == 1) { a.push_back(v[0]); b.push_back(v[1]); } else if (q == 2) { b.push_back(v[0]); a.push_back(v[1]); } } else { int q = use_machine({b[0], v[0], b[1], v[1]}); if (q == 0) { b.push_back(v[0]); b.push_back(v[1]); } else if (q == 3) { a.push_back(v[0]); a.push_back(v[1]); } else if (q == 1) { b.push_back(v[0]); a.push_back(v[1]); } else if (q == 2) { a.push_back(v[0]); b.push_back(v[1]); } } reverse(all(v)); v.pop_back(); v.pop_back(); } int ans = sz(a); for (int i = M; i < n; ++i) v.push_back(i); while (!v.empty()) { if (sz(a) > sz(b)) { if (sz(v) <= sz(a)) { vector<int> x; for (int i = 0; i < sz(v); ++i) { x.push_back(a[i]); x.push_back(v[i]); } int q = use_machine(x); ans += (sz(v) - 1 - q / 2); if (q % 2 == 0) { ++ans; a.push_back(v.back()); } else { b.push_back(v.back()); } v.clear(); } else { vector<int> u; for (int i = 0; i < sz(a); ++i) { u.push_back(v.back()); v.pop_back(); } vector<int> x; for (int i = 0; i < sz(u); ++i) { x.push_back(a[i]); x.push_back(u[i]); } int q = use_machine(x); ans += (sz(u) - 1 - q / 2); if (q % 2 == 0) { ++ans; a.push_back(u.back()); } else { b.push_back(u.back()); } u.clear(); } } else { if (sz(v) <= sz(b)) { vector<int> x; for (int i = 0; i < sz(v); ++i) { x.push_back(b[i]); x.push_back(v[i]); } int q = use_machine(x); ans += q / 2; if (q % 2 == 0) { b.push_back(v.back()); } else { ++ans; a.push_back(v.back()); } v.clear(); } else { vector<int> u; for (int i = 0; i < sz(b); ++i) { u.push_back(v.back()); v.pop_back(); } vector<int> x; for (int i = 0; i < sz(u); ++i) { x.push_back(b[i]); x.push_back(u[i]); } int q = use_machine(x); ans += q / 2; if (q % 2 == 0) { b.push_back(u.back()); } else { ++ans; a.push_back(u.back()); } u.clear(); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...