Submission #1195461

#TimeUsernameProblemLanguageResultExecution timeMemory
1195461avighnaMinerals (JOI19_minerals)C++20
80 / 100
18 ms2084 KiB
#include "minerals.h" #include <algorithm> #include <numeric> #include <vector> #include <random> void Solve(int n) { int pr = Query(1); std::vector<int> set1 = {1}, set2; for (int i = 2; i <= 2 * n; ++i) { int ne = Query(i); (pr != ne ? set1 : set2).push_back(i); pr = ne; } std::random_device rd; std::mt19937 rng(rd()); // before dnc: set1 == set2 // make dnc step make it so // set1 left half == set2 left half (then set1 right half is automatically == set2 right half) auto solve = [&](auto &&self, int l, int r, bool added) { if (l == r) { Answer(set1[l], set2[l]); return; } int m = l + (r - l) * 0.5; // add to machine if (added) { // remove right half for (int i = m + 1; i <= r; ++i) { pr = Query(set1[i]); } } else { for (int i = l; i <= m; ++i) { pr = Query(set1[i]); } } // now both parts are good int trues = 0; std::shuffle(set2.begin() + l, set2.begin() + r + 1, rng); std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) { if (trues >= m - l + 1) { return false; } int ne = Query(x); bool unchanged = pr == ne; pr = ne; trues += unchanged; return unchanged; }); // do dnc self(self, l, m, true); self(self, m + 1, r, false); }; solve(solve, 0, n - 1, true); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...