제출 #604761

#제출 시각아이디문제언어결과실행 시간메모리
604761SamAnd버섯 세기 (IOI20_mushrooms)C++17
0 / 100
1 ms208 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 = 200; 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); for (int i = 0; i < sz(v); ++i) { if (use_machine({0, v[i]}) == 0) a.push_back(v[i]); else b.push_back(v[i]); } /*while (!v.empty()) { if (sz(v) == 1) { int q = use_machine({0, v[0]}); if (q == 0) { a.push_back(v[0]); } else { b.push_back(v[0]); } v.pop_back(); break; } for (int i = sz(v) - 1; i >= 0; --i) { swap(v[i], v[rnf() % (i + 1)]); } int q = use_machine({v[0], 0, v[1]}); if (q == 0) { a.push_back(v[0]); a.push_back(v[1]); } else if (q == 2) { b.push_back(v[0]); b.push_back(v[1]); } else { q = use_machine({v[0], 0}); if (q == 0) { a.push_back(v[0]); b.push_back(v[1]); } else { a.push_back(v[1]); b.push_back(v[0]); } } 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...