Submission #1128650

#TimeUsernameProblemLanguageResultExecution timeMemory
1128650vladiliusMinerals (JOI19_minerals)C++20
85 / 100
27 ms2784 KiB
#include <bits/stdc++.h> #include "minerals.h" using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second void Solve(int n){ vector<bool> us(2 * n + 1); int S = 0; for (int i = 1; i <= 2 * n; i++){ if (Query(i) > S){ S++; us[i] = 1; } } vector<int> lf = {0}, rr; for (int i = 1; i <= 2 * n; i++){ if (us[i]){ lf.pb(i); continue; } rr.pb(i); } int tr = n; S = n; function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> f){ if (l == r){ Answer(lf[l], f[0]); return; } int m = (l + r) / 2; while (tr < m){ S = Query(lf[++tr]); } while (tr > m){ S = Query(lf[tr--]); } vector<int> left, right; for (int j = 0; j + 1 < f.size(); j++){ int i = f[j]; if (left.size() == (m - l + 1)){ right.pb(i); continue; } if (right.size() == (r - m)){ left.pb(i); continue; } int S1 = Query(i); if (S1 == S){ left.pb(i); } else { S = S1; right.pb(i); } } if (left.size() <= (m - l)) left.pb(f.back()); else right.pb(f.back()); solve(m + 1, r, right); solve(l, m, left); }; solve(1, n, rr); }
#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...