Submission #805065

#TimeUsernameProblemLanguageResultExecution timeMemory
805065LittleCubeCounting Mushrooms (IOI20_mushrooms)C++17
80.43 / 100
8 ms316 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int k = 142; int count_mushrooms(int n) { int A = 0, B = 0; // small case if (n <= 226) { A = 1; for (int i = 1; i < n; i++) if (!use_machine({0, i})) A++; return A; } vector<int> a, b; a.emplace_back(0); for (int i = 1; i < 3; i++) if (use_machine({0, i})) b.push_back(i); else a.push_back(i); if (a.size() >= 2) { int a1 = a[0], a2 = a[1]; for (int i = 3; i < 2 * k - 1; i += 2) { int result = use_machine({a1, i, a2, i + 1}); if (result == 0) a.push_back(i), a.push_back(i + 1); else if (result == 1) a.push_back(i), b.push_back(i + 1); else if (result == 2) b.push_back(i), a.push_back(i + 1); else if (result == 3) b.push_back(i), b.push_back(i + 1); } } else { int b1 = b[0], b2 = b[1]; for (int i = 3; i < 2 * k - 1; i += 2) { int result = use_machine({b1, i, b2, i + 1}); if (result == 3) a.push_back(i), a.push_back(i + 1); else if (result == 2) a.push_back(i), b.push_back(i + 1); else if (result == 1) b.push_back(i), a.push_back(i + 1); else if (result == 0) b.push_back(i), b.push_back(i + 1); } } // not too small case if (n <= 2 * k - 1) return a.size(); // big case if (a.size() >= k) { for (int i = 2 * k - 1; i < n; i += k) { vector<int> q; for (int j = 0; j < k && i + j < n; j++) { q.emplace_back(a[j]); q.emplace_back(i + j); } B += (use_machine(q) + 1) / 2; } return n - (int)b.size() - B; } else { for (int i = 2 * k - 1; i < n; i += k) { vector<int> q; for (int j = 0; j < k && i + j < n; j++) { q.emplace_back(b[j]); q.emplace_back(i + j); } A += (use_machine(q) + 1) / 2; } return a.size() + A; } }
#Verdict Execution timeMemoryGrader output
Fetching results...