Submission #818035

#TimeUsernameProblemLanguageResultExecution timeMemory
818035eltu0815Counting Mushrooms (IOI20_mushrooms)C++14
100 / 100
7 ms372 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define X 44 using namespace std; int arr[20005]; vector<int> A, B; int count_mushrooms(int n) { std::vector<int> m; if(n < 5 * X) { for(int i = 1; i < n; ++i) { m.clear(); m.push_back(i); m.push_back(i - 1); if(use_machine(m) == 1) arr[i] = !arr[i - 1]; else arr[i] = arr[i - 1]; } int ans = 0; for(int i = 0; i < n; ++i) if(arr[i] == 0) ++ans; return ans; } for(int i = 1; i <= 2; ++i) { m.clear(); m.push_back(i - 1); m.push_back(i); if(use_machine(m) == 1) arr[i] = !arr[i - 1]; else arr[i] = arr[i - 1]; } int n1, n2; if(arr[0] == arr[1]) n1 = 0, n2 = 1; else if(arr[0] == arr[2]) n1 = 0, n2 = 2; else n1 = 1, n2 = 2; m.clear(); m.push_back(n1); m.push_back(3); m.push_back(n2); m.push_back(4); int tmp = use_machine(m); if(tmp == 0) arr[3] = arr[4] = arr[n1]; if(tmp == 1) arr[3] = arr[n1], arr[4] = !arr[n1]; if(tmp == 2) arr[3] = !arr[n1], arr[4] = arr[n1]; if(tmp == 3) arr[3] = arr[4] = !arr[n1]; for(int i = 0; i < 5; ++i) { if(arr[i] == 0) A.push_back(i); else B.push_back(i); } for(int i = 5; i < 5 * X; i += 5) { if(A.size() >= 3) { m.clear(); m.push_back(A[0]); m.push_back(i); m.push_back(A[1]); m.push_back(i + 1); m.push_back(A[2]); m.push_back(i + 2); int tmp = use_machine(m); if(tmp == 0) arr[i] = arr[i + 1] = arr[i + 2] = 0; if(tmp == 1) arr[i] = arr[i + 1] = 0, arr[i + 2] = 1; if(tmp == 4) arr[i] = arr[i + 1] = 1, arr[i + 2] = 0; if(tmp == 5) arr[i] = arr[i + 1] = arr[i + 2] = 1; if(tmp == 2) arr[i + 2] = 0; if(tmp == 3) arr[i + 2] = 1; if(tmp == 2 || tmp == 3) { if(B.size() >= 2) { m.clear(); m.push_back(B[0]); m.push_back(i); m.push_back(B[1]); m.push_back(A[0]); m.push_back(i + 1); m.push_back(A[1]); m.push_back(i + 3); m.push_back(A[2]); m.push_back(i + 4); int tmp = use_machine(m); --tmp; if(tmp < 4) arr[i] = 1, arr[i + 1] = 0; else arr[i] = 0, arr[i + 1] = 1; tmp %= 4; if(tmp == 0) arr[i + 3] = arr[i + 4] = 0; if(tmp == 1) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 2) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 3) arr[i + 3] = arr[i + 4] = 1; } else { m.clear(); m.push_back(A[0]); m.push_back(i); int tmp = use_machine(m); if(tmp == 1) arr[i] = 1, arr[i + 1] = 0; else arr[i] = 0, arr[i + 1] = 1; m.clear(); m.push_back(A[0]); m.push_back(i + 3); m.push_back(A[1]); m.push_back(i + 4); tmp = use_machine(m); if(tmp == 0) arr[i + 3] = arr[i + 4] = 0; if(tmp == 1) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 2) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 3) arr[i + 3] = arr[i + 4] = 1; } } else { m.clear(); m.push_back(A[0]); m.push_back(i + 3); m.push_back(A[1]); m.push_back(i + 4); int tmp = use_machine(m); if(tmp == 0) arr[i + 3] = arr[i + 4] = 0; if(tmp == 1) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 2) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 3) arr[i + 3] = arr[i + 4] = 1; } } else { m.clear(); m.push_back(B[0]); m.push_back(i); m.push_back(B[1]); m.push_back(i + 1); m.push_back(B[2]); m.push_back(i + 2); int tmp = use_machine(m); if(tmp == 0) arr[i] = arr[i + 1] = arr[i + 2] = 1; if(tmp == 1) arr[i] = arr[i + 1] = 1, arr[i + 2] = 0; if(tmp == 4) arr[i] = arr[i + 1] = 0, arr[i + 2] = 1; if(tmp == 5) arr[i] = arr[i + 1] = arr[i + 2] = 0; if(tmp == 2) arr[i + 2] = 1; if(tmp == 3) arr[i + 2] = 0; if(tmp == 2 || tmp == 3) { if(A.size() >= 2) { m.clear(); m.push_back(A[0]); m.push_back(i); m.push_back(A[1]); m.push_back(B[0]); m.push_back(i + 1); m.push_back(B[1]); m.push_back(i + 3); m.push_back(B[2]); m.push_back(i + 4); int tmp = use_machine(m); --tmp; if(tmp < 4) arr[i] = 0, arr[i + 1] = 1; else arr[i] = 1, arr[i + 1] = 0; tmp %= 4; if(tmp == 0) arr[i + 3] = arr[i + 4] = 1; if(tmp == 1) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 2) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 3) arr[i + 3] = arr[i + 4] = 0; } else { m.clear(); m.push_back(B[0]); m.push_back(i); int tmp = use_machine(m); if(tmp == 1) arr[i] = 0, arr[i + 1] = 1; else arr[i] = 1, arr[i + 1] = 0; m.clear(); m.push_back(B[0]); m.push_back(i + 3); m.push_back(B[1]); m.push_back(i + 4); tmp = use_machine(m); if(tmp == 0) arr[i + 3] = arr[i + 4] = 1; if(tmp == 1) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 2) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 3) arr[i + 3] = arr[i + 4] = 0; } } else { m.clear(); m.push_back(B[0]); m.push_back(i + 3); m.push_back(B[1]); m.push_back(i + 4); int tmp = use_machine(m); if(tmp == 0) arr[i + 3] = arr[i + 4] = 1; if(tmp == 1) arr[i + 3] = 1, arr[i + 4] = 0; if(tmp == 2) arr[i + 3] = 0, arr[i + 4] = 1; if(tmp == 3) arr[i + 3] = arr[i + 4] = 0; } } for(int j = i; j < i + 5; ++j) { if(arr[j] == 0) A.push_back(j); else B.push_back(j); } } int ans = 0; for(int i = 0; i < 5 * X; ++i) if(arr[i] == 0) ++ans; int nxt = 0; for(int i = 5 * X; i < n; i += nxt) { if(i + (int)max(A.size(), B.size()) <= n) { m.clear(); for(int j = i; j < i + (int)max(A.size(), B.size()); ++j) { m.push_back(j); if(A.size() >= B.size()) m.push_back(A[j - i]); else m.push_back(B[j - i]); } int tmp = use_machine(m); int cnt = (tmp % 2) + (tmp / 2); if(A.size() >= B.size()) ans += (int)A.size() - cnt; else ans += cnt; nxt = (int)max(A.size(), B.size()); if(tmp % 2 == 1) { if(A.size() >= B.size()) B.push_back(i); else A.push_back(i); } else { if(A.size() >= B.size()) A.push_back(i); else B.push_back(i); } } else { m.clear(); for(int j = i; j < n; ++j) { m.push_back(j); if(A.size() >= B.size()) m.push_back(A[j - i]); else m.push_back(B[j - i]); } int tmp = use_machine(m); int cnt = (tmp % 2) + (tmp / 2); if(A.size() >= B.size()) ans += n - i - cnt; else ans += cnt; break; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...