Submission #1190233

#TimeUsernameProblemLanguageResultExecution timeMemory
1190233Ghulam_JunaidMinerals (JOI19_minerals)C++20
0 / 100
1 ms2780 KiB
#include <bits/stdc++.h> #include "minerals.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MXN = 1e5 + 100; int n, lo[MXN], hi[MXN]; vector<int> a, b, vec[MXN]; set<int> M; void Solve(int nn){ srand(time(NULL)); n = nn; vector<int> S; for (int i = 1; i <= 2 * n; i ++) S.push_back(i); for (int i = 2 * n; i > 0; i --) swap(S[i - 1], S[rng() % i]); int D = 0; for (int i : S){ if (Query(i) == D){ b.push_back(i); } else{ D++; a.push_back(i); } } for (int i : a){ lo[i] = -1; hi[i] = n - 1; } for (int i : a){ if (hi[i] - lo[i] <= 1) continue; int mid = (lo[i] + hi[i]) / 2; M.insert(mid); vec[mid].push_back(i); } int it = 1; int fst = 0, lst = n - 1; while (!M.empty()){ it++; if (it % 2 == 1){ for (int i = fst; i < n; i ++){ D = Query(b[i]); int tmpD; for (int x : vec[i]){ tmpD = Query(x); if (tmpD == D) hi[x] = i; else lo[x] = i; D = tmpD; if (hi[x] - lo[x] > 1){ int mid = (lo[x] + hi[x]) / 2; vec[mid].push_back(x); M.insert(mid); } } M.erase(i); vec[i].clear(); lst = i; if (M.empty() or (*M.rbegin()) <= i) break; } } else{ int tmpD; for (int i = lst; i >= 0; i --){ for (int x : vec[i]){ tmpD = Query(x); if (tmpD == D) hi[x] = i; else lo[x] = i; D = tmpD; if (hi[x] - lo[x] > 1){ int mid = (lo[x] + hi[x]) / 2; vec[mid].push_back(x); } } vec[i].clear(); D = Query(b[i]); fst = i; if (M.empty() or *M.begin() >= i) break; } } } for (int i : a) Answer(i, b[hi[i]]); }
#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...