Submission #876323

#TimeUsernameProblemLanguageResultExecution timeMemory
876323KanonCounting Mushrooms (IOI20_mushrooms)C++14
88.28 / 100
5 ms804 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; const int magic = 84; const int bound = 226; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng) // random shuffle : shuffle(.begin(), .end(), rng) int count_mushrooms(int n) { if (n <= bound + 1) { int ret = 1; for (int i = 1; i < n; i++) { ret += use_machine({0, i}) ^ 1; } return ret; } vector<int> a(n, -1); a[0] = 0; vector<int> order(magic); iota(order.begin(), order.end(), 1); shuffle(order.begin(), order.end(), rng); int cnt = magic + 1; int iter = 1; map<int, vector<int>> best_choice; while (iter--) { order.insert(order.begin(), 0); order.push_back(cnt++); int st = use_machine(order); a[cnt - 1] = a[0] ^ (st & 1); best_choice[st] = order; int sz = order.size() / (st + 1); vector<int> Lorder, Rorder; for (int i = 1; i < (int) order.size() - 1; i++) { int md = i % (2 * sz); if (md >= sz) Rorder.push_back(order[i]); else Lorder.push_back(order[i]); } shuffle(Lorder.begin(), Lorder.end(), rng); shuffle(Rorder.begin(), Rorder.end(), rng); order = Lorder; order.insert(order.end(), Rorder.begin(), Rorder.end()); } int st = best_choice.begin()->first; order = best_choice.begin()->second; vector<int> ONE, ZERO; ZERO.push_back(0); for (int i = 0; i < 2; i++) { a[cnt] = (use_machine({0, cnt}) & 1) ^ a[0]; cnt++; if (a[cnt - 1] == 0) ZERO.push_back(cnt - 1); else ONE.push_back(cnt - 1); } function<void(int, int, int, vector<int>)> dfs = [&](int vL, int vR, int tot, vector<int> p) { assert(vL != -1 && vR != -1 && vL == a[p[0]] && vR == a[p.back()]); assert(0 <= tot && tot <= (int) p.size() - 1); if (p.size() <= 2) return; if (tot == 0) { for (int i = 1; i < (int) p.size() - 1; i++) a[p[i]] = a[p[i - 1]]; return; } if (tot == (int) p.size() - 1) { for (int i = 1; i < (int) p.size() - 1; i++) a[p[i]] = a[p[i - 1]] ^ 1; return; } int sz = p.size(); int mid = (sz + 1) / 2; assert(mid > 1); if (mid > 2) { vector<int> que(p.begin(), p.begin() + mid); que.push_back(cnt++); int st = use_machine(que); a[cnt - 1] = vL ^ (st & 1); dfs(vL, a[cnt - 1], st, que); for (int i = 1; i < mid; i++) { int u = que[i], v = que[i - 1]; tot -= a[u] ^ a[v]; } } else { vector<int> pii = ONE.size() >= 2 ? ONE : ZERO; int st = use_machine({pii[0], p[mid - 1], pii[1], cnt++}); a[cnt - 1] = a[pii[0]] ^ (st & 1); st -= a[pii[1]] ^ a[cnt - 1]; if (st > 0) a[p[mid - 1]] = a[pii[0]] ^ 1; else a[p[mid - 1]] = a[pii[0]]; tot -= a[p[mid - 1]] ^ a[p[0]]; } vector<int> que = vector<int>(p.begin() + mid - 1, p.end()); dfs(a[p[mid - 1]], vR, tot, que); }; dfs(a[0], a[order.back()], st, order); int ret = 0; vector<int> zeros, ones; for (int i = 0; i < cnt; i++) { if (a[i] == 0) zeros.push_back(i); else ones.push_back(i); } ret += zeros.size(); while (cnt < n) { int len = min(n - cnt, (int) max(zeros.size(), ones.size())); vector<int> ids = zeros.size() >= ones.size() ? zeros : ones; vector<int> que; for (int i = 0; i < len; i++) { que.push_back(ids[i]); que.push_back(cnt++); } int st = use_machine(que); if (ids == ones) { a[cnt - 1] = 1 ^ (st & 1); ret += a[cnt - 1] == 0; st -= a[cnt - 1] == 0; if (a[cnt - 1] == 0) zeros.push_back(cnt - 1); else ones.push_back(cnt - 1); assert(st % 2 == 0); ret += st >> 1; } else { a[cnt - 1] = 0 ^ (st & 1); ret += a[cnt - 1] == 0; st -= a[cnt - 1] == 1; if (a[cnt - 1] == 0) zeros.push_back(cnt - 1); else ones.push_back(cnt - 1); assert(st % 2 == 0); ret += (len - 1) - (st >> 1); } } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...