Submission #1114986

#TimeUsernameProblemLanguageResultExecution timeMemory
1114986zsomborCounting Mushrooms (IOI20_mushrooms)C++17
80.14 / 100
10 ms608 KiB
#include "mushrooms.h" using namespace std; int x, y, q, l = 3, c, ans, z = 139; vector <vector <int>> v(2); vector <int> u; int count_mushrooms(int n) { if (n == 2) return 2 - use_machine({ 0, 1 }); v[0].push_back(0); v[use_machine({ 0,1 })].push_back(1); v[use_machine({ 0,2 })].push_back(2); if (v[1].size() >= 2) x = 1; for (int i = 3; i < min(n - 1, 2 * z + 1); i += 2) { q = use_machine({ v[x][0], i, v[x][1], i + 1 }); v[(q / 2) ^ x].push_back(i); v[(q % 2) ^ x].push_back(i + 1); l = i + 2; } if (v[1].size() > v[0].size()) y = 1; ans = v[0].size(); while (l < n) { u = { v[y][0] }; c = 0; while (l < n && c < z) { u.push_back(l++); u.push_back(v[y][++c]); } q = use_machine(u) / 2; ans += (y ? q : c - q); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...