Submission #1248050

#TimeUsernameProblemLanguageResultExecution timeMemory
1248050rythm_of_knightMinerals (JOI19_minerals)C++17
100 / 100
336 ms3948 KiB
#include "minerals.h" #include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; const int MXN = 43043, inf = 1e7; vector <int> a, b; static int cnt = 0, n, m; int lg[MXN << 1], dp[MXN][2], mid[MXN][2]; void rec(int l, int r, int k, vector <int> q) { if (l == r) return Answer(a[l], q[0]), void(); int m = l + mid[r - l + 1][k], lk = k, rk = k; vector <int> lft, rgt; int lneed = m - l + 1, rneed = r - m; if (k) { for (int i = m + 1; i <= r; i++) cnt = Query(a[i]); rk ^= 1; } else { for (int i = l; i <= m; i++) cnt = Query(a[i]); lk ^= 1; } for (int j : q) { if (lft.size() == lneed) { rgt.push_back(j); } else if (rgt.size() == rneed) { lft.push_back(j); } else { int tmp = Query(j); if (tmp == cnt) { lft.push_back(j); } else { rgt.push_back(j); } cnt = tmp; } } rec(l, m, lk, lft); rec(m + 1, r, rk, rgt); } void Solve(int N) { n = N, m = 2 * n; lg[0] = -1; for (int i = 1; i <= m; i++) lg[i] = lg[i >> 1] + 1; for (int i = 1; i <= m; i++) { int tmp = Query(i); if (tmp != cnt) a.push_back(i); else b.push_back(i); cnt = tmp; } for (int i = 2; i <= n; i++) { dp[i][0] = dp[i][1] = inf; int md = i >> 1; int tl = max(0, md - 3000); int tr = min(i - 2, md + 3000); for (int j = tl; j <= tr; j++) { if (dp[i][1] > dp[j + 1][1] + dp[i - j - 1][0] + i - j - 1) { dp[i][1] = dp[j + 1][1] + dp[i - j - 1][0] + i - j - 1; mid[i][1] = j; } } dp[i][1] += i - 1; for (int j = tl; j <= tr; j++) { if (dp[i][0] > dp[j + 1][1] + dp[i - j - 1][0] + j + 1) { dp[i][0] = dp[j + 1][1] + dp[i - j - 1][0] + j + 1; mid[i][0] = j; } } dp[i][0] += i - 1; } // cout << dp[n][0] << ' ' << mid[n][0] << '\n'; rec(0, n - 1, 1, b); }
#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...