Submission #1195454

#TimeUsernameProblemLanguageResultExecution timeMemory
1195454avighnaMinerals (JOI19_minerals)C++20
80 / 100
14 ms2768 KiB
#include "minerals.h" #include <algorithm> #include <numeric> #include <vector> void Solve(int n) { int old = Query(1); std::vector<int> distinct = {1}, repeated; for (int i = 2; i <= 2 * n; ++i) { int nval = Query(i); if (old != nval) { distinct.push_back(i); } else { repeated.push_back(i); } old = nval; } std::vector<int> p(2 * n + 1); for (int i = 1; i <= n; ++i) { p[i] = distinct[i - 1]; } for (int i = n + 1; i <= 2 * n; ++i) { p[i] = repeated[i - n - 1]; } auto query = [&](int i) { return Query(p[i]); }; auto answer = [&](int a, int b) { Answer(p[a], p[b]); }; std::vector<int> set1(n), set2(n); std::iota(set1.begin(), set1.end(), 1); std::iota(set2.begin(), set2.end(), n + 1); // 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) int pr = -1; auto solve = [&](auto &&self, int l, int r, bool added) { if (l == r) { answer(set1[l], set2[l]); return; } int m = (l + r) / 2; // 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 std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) { int ne = query(x); bool unchanged = pr == ne; pr = ne; 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...