제출 #605027

#제출 시각아이디문제언어결과실행 시간메모리
605027SamAnd버섯 세기 (IOI20_mushrooms)C++17
79.58 / 100
12 ms508 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 = 300; 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); if (sz(a) > sz(b)) { while (!v.empty()) { if (sz(v) < sz(a)) { vector<int> x; x.push_back(a[0]); for (int i = 0; i < sz(v); ++i) { x.push_back(v[i]); x.push_back(a[i + 1]); } ans += (sz(v) - use_machine(x) / 2); v.clear(); } else { vector<int> u; for (int i = 0; i < sz(a) - 1; ++i) { u.push_back(v.back()); v.pop_back(); } vector<int> x; x.push_back(a[0]); for (int i = 0; i < sz(u); ++i) { x.push_back(u[i]); x.push_back(a[i + 1]); } ans += (sz(u) - use_machine(x) / 2); u.clear(); } } } else { while (!v.empty()) { if (sz(v) < sz(b)) { vector<int> x; x.push_back(b[0]); for (int i = 0; i < sz(v); ++i) { x.push_back(v[i]); x.push_back(b[i + 1]); } ans += use_machine(x) / 2; v.clear(); } else { vector<int> u; for (int i = 0; i < sz(b) - 1; ++i) { u.push_back(v.back()); v.pop_back(); } vector<int> x; x.push_back(b[0]); for (int i = 0; i < sz(u); ++i) { x.push_back(u[i]); x.push_back(b[i + 1]); } ans += use_machine(x) / 2; u.clear(); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...