Submission #916248

#TimeUsernameProblemLanguageResultExecution timeMemory
916248boris_mihovMinerals (JOI19_minerals)C++17
0 / 100
1 ms600 KiB
#include "minerals.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <random> #include <vector> #include <queue> typedef long long llong; const int MAXN = 86000 + 10; const int INF = 1e9; int n; struct Node { int idx; int level; int l, r; int qL, qR; }; int perm[MAXN]; std::vector <int> unique; std::vector <int> second; std::vector <int> secondCopy; std::queue <Node> waitlist; std::mt19937 rng(69420); int countDiff; int query(int idx) { return countDiff = Query(perm[idx]); } void answer(int a, int b) { Answer(perm[a], perm[b]); } void Solve(int N) { n = N; std::iota(perm + 1, perm + 1 + 2 * n, 1); std::shuffle(perm + 1, perm + 1 + 2 * n, rng); unique.push_back(0); unique.push_back(1); second.push_back(0); query(1); int last = 1; for (int i = 2 ; i <= 2 * n ; ++i) { if (query(i) > last) { last++; unique.push_back(i); } else { second.push_back(i); } } for (int i = 1 ; i <= n ; ++i) { query(second[i]); } waitlist.push({1, 1, 1, n, 1, n}); assert(unique.size() == n + 1); assert(second.size() == n + 1); secondCopy.resize(n + 1); int ptr = n; int lastLevel = 1; while (waitlist.size()) { auto [idx, level, l, r, qL, qR] = waitlist.front(); waitlist.pop(); assert(r - l + 1 == qR - qL + 1); if (l == r) { assert(qL == qR); answer(unique[l], second[qL]); continue; } if (level != lastLevel) { if (level & 1) { while (ptr < n) { query(unique[ptr]); ptr++; } } else { while (ptr > 0) { query(unique[ptr]); ptr--; } } } int mid = (l + r) / 2; if (level & 1) { while (ptr > mid) { query(unique[ptr]); ptr--; } } else { while (ptr < mid) { ptr++; query(unique[ptr]); } } int myL = qL; int myR = qR; for (int idx = qL ; idx <= qR ; ++idx) { int last = countDiff; int curr = query(second[idx]); if (curr == last) { secondCopy[myL++] = second[idx]; } else { secondCopy[myR--] = second[idx]; } query(second[idx]); } for (int idx = qL ; idx <= qR ; ++idx) { second[idx] = secondCopy[idx]; } assert(qL < myL); assert(myR < qR); if (qL != myL) waitlist.push({2 * idx, level + 1, l, mid, qL, myL - 1}); if (qR != myR) waitlist.push({2 * idx + 1, level + 1, mid + 1, r, myR + 1, qR}); } }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from minerals.cpp:5:
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:71:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     assert(unique.size() == n + 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~
minerals.cpp:72:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     assert(second.size() == n + 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~
#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...