#include "books.h"
#include <bits/stdc++.h>
using namespace std;
int n, cnt[1000009];
long long solve_subtask3(vector<int>p, int s) {
n = p.size(); int maxn = 0;
for (int i = 0; i < n; i++) {
int u = i, v = p[i]; if (u > v) swap(u, v); if (u != v) { maxn = max(maxn, max(u, v)); }
cnt[u]++; cnt[v]--;
}
for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
long long sum = 0; for (int i = 0; i < n; i++) sum += 1LL * abs(p[i] - i);
for (int i = 0; i < maxn; i++) { if (cnt[i] == 0) sum += 2; }
return sum;
}
vector<int> G[1009]; int cnts;
bool used[1009]; int cl[1009], cr[1009], pre[1009][1009], dp[1009][1009];
pair<int, int> nex[1009][1009];
long long solve_subtask4(vector<int> p, int s) {
n = p.size(); int gl = n - 1, gr = 0;
for (int i = 0; i < n; i++) {
if (used[i] == true || p[i] == i) continue;
gl = min(gl, i); gr = max(gr, i);
int cx = i; cl[cnts] = n - 1; cr[cnts] = 0;
while (used[cx] == false) {
used[cx] = true;
G[cnts].push_back(cx);
cl[cnts] = min(cl[cnts], cx);
cr[cnts] = max(cr[cnts], cx);
cx = p[cx];
}
cnts++;
}
if (gl > gr) return 0;
// ------------------------ DP の前処理 --------------------------
for (int i = 0; i < cnts; i++) { for (int j = 0; j <= n; j++) pre[i][j] = n; }
for (int i = 0; i < cnts; i++) {
for (int j : G[i]) pre[i][j] = j;
}
for (int i = 0; i < cnts; i++) {
for (int j = n - 1; j >= 0; j--) pre[i][j] = min(pre[i][j], pre[i][j + 1]);
}
for (int pl = 0; pl < n; pl++) {
for (int pr = pl; pr < n; pr++) {
nex[pl][pr] = make_pair(pl, pr);
for (int k = 0; k < cnts; k++) {
if (pl <= cl[k] && cr[k] <= pr) continue;
if (pre[k][pl] > pr) continue;
nex[pl][pr] = make_pair(min(cl[k], pl), max(cr[k], pr));
break;
}
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n - i; j++) {
int pl = j, pr = j + i;
nex[pl][pr] = nex[nex[pl][pr].first][nex[pl][pr].second];
}
}
// ---------------------- DP の遷移 ---------------------
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) dp[i][j] = (1 << 30); }
dp[nex[s][s].first][nex[s][s].second] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
int pl = j, pr = j + i;
if (dp[pl][pr] == (1 << 30)) continue;
pair<int, int> minx = make_pair((1 << 25), 0);
for (int k = 0; k < cnts; k++) {
if (cl[k] == cr[k]) continue;
if (pl <= cl[k] && cr[k] <= pr) continue;
int pos1 = lower_bound(G[k].begin(), G[k].end(), pl) - G[k].begin(); pos1--;
int pos2 = lower_bound(G[k].begin(), G[k].end(), pr + 1) - G[k].begin();
int rem = (1 << 30);
if (pos1 >= 0) rem = min(rem, pl - G[k][pos1]);
if (pos2 < G[k].size()) rem = min(rem, G[k][pos2] - pr);
minx = min(minx, make_pair(rem, k));
}
int el = min(pl, cl[minx.second]), er = max(pr, cr[minx.second]);
int fl = nex[el][er].first, fr = nex[el][er].second;
dp[fl][fr] = min(dp[fl][fr], dp[pl][pr] + 2 * minx.first);
}
}
long long addition = 0;
for (int i = 0; i < n; i++) addition += abs(p[i] - i);
return dp[0][n - 1] + addition;
}
long long minimum_walk(vector<int> p, int s) {
if (p.size() <= 1000) return solve_subtask4(p, s);
return solve_subtask3(p, s);
}
Compilation message
books.cpp: In function 'long long int solve_subtask4(std::vector<int>, int)':
books.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos2 < G[k].size()) rem = min(rem, G[k][pos2] - pr);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '4', found: '1073741828' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '4', found: '1073741828' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '4', found: '1073741828' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
12024 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3372' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '4', found: '1073741828' |
| 6 |
Halted |
0 ms |
0 KB |
- |
