Submission #315441

#TimeUsernameProblemLanguageResultExecution timeMemory
315441nonthaphatCounting Mushrooms (IOI20_mushrooms)C++14
100 / 100
13 ms544 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; int seed = time(0); bool swapped = false; int i = 1; int just_count_A = 0; int just_count_B = 0; vector<int> A = { 0 }; vector<int> B = { }; vector<int> idx; int calc_pivots_size(int n) { return 1 + 3*sqrt(n)/4; } void make_swap() { swapped = not swapped; swap(just_count_A, just_count_B); swap(A, B); } bool decide_swap() { if (A.size() < B.size()) { make_swap(); } return true; } int handle_parity(int parity) { (parity == 0 ? A : B).push_back(idx[i]); return 1; } int handle_pair(int raw_info) { int even024 = raw_info - (raw_info%2); if (even024 == 2) { throw invalid_argument("conflict: need more info to handle this case"); } (even024 == 0 ? A : B).push_back(idx[i]); (even024 == 0 ? A : B).push_back(idx[i+1]); return 2; } int handle_conflict_pair(int raw_info) { int flag3b = raw_info - 1; (flag3b & 0b100 ? A : B).push_back(idx[i]); (flag3b & 0b100 ? B : A).push_back(idx[i+1]); (flag3b & 0b010 ? B : A).push_back(idx[i+2]); (flag3b & 0b001 ? B : A).push_back(idx[i+3]); return 4; } void get_pivots(int n) { int info; int size = calc_pivots_size(n); while (decide_swap() and (int)A.size() < size and i+5 < n) { if (A.size() < 2) { i += handle_parity(use_machine({ idx[i], A[0] })); } else if (A.size() < 3 or B.size() < 2) { info = use_machine({ idx[i], A[0], idx[i+1], A[1] }); i += handle_parity(info%2); i += handle_parity(info/2); } else { info = use_machine({ idx[i], A[0], idx[i+1], A[1], idx[i+2], A[2] }); i += handle_parity(info%2); try { i += handle_pair(info); } catch (const invalid_argument &) { info = use_machine({ B[0], idx[i], B[1], A[0], idx[i+1], A[1], idx[i+2], A[2], idx[i+3] }); i += handle_conflict_pair(info); } } } } vector<int> make_sample(int size) { vector<int> sample = { }; for (int j=0; j<size; j++) { sample.insert(sample.end(), { idx[i+j], A[j] }); } return sample; } void count_the_rest(int n) { while (decide_swap() and i < n) { int test_size = min((int)A.size(), n-i); int info = use_machine(make_sample(test_size)); i += handle_parity(info%2); i += test_size-1; just_count_A += (test_size-1) - (info/2); just_count_B += info/2; } } int count_mushrooms(int n) { srand(seed); idx.push_back(0); for(int i=1;i<n;i++) idx.push_back(i); random_shuffle(idx.begin()+1, idx.end()); get_pivots(n); count_the_rest(n); if (swapped) { make_swap(); } return A.size() + just_count_A; }
#Verdict Execution timeMemoryGrader output
Fetching results...