#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[1000009]; int cnts;
bool used[1000009]; int cl[1000009], cr[1000009];
long long solve_subtask4(vector<int> p, int s) {
n = p.size();
for (int i = 0; i < n; i++) {
if (used[i] == true) continue;
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++;
}
for (int i = 0; i < cnts; i++) sort(G[i].begin(), G[i].end());
int pl = s, pr = s; long long totalcost = 0;
while (true) {
bool flag = false; int ret = 0;
for (int i = 0; i < cnts; i++) {
if (cl[i] == cr[i]) continue;
if (pl <= cl[i] && cr[i] <= pr) continue;
ret++;
int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin();
int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
if (pos2 - pos1 >= 1) { pl = min(pl, cl[i]); pr = max(pr, cr[i]); flag = true; }
}
if (ret == 0) break;
if (flag == true) continue;
pair<long long, int> minx = make_pair((1 << 30), 0);
for (int i = 0; i < cnts; i++) {
if (cl[i] == cr[i]) continue;
if (pl <= cl[i] && cr[i] <= pr) continue;
int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin(); pos1--;
int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
long long rem = (1 << 30);
if (pos1 >= 0) rem = min(rem, 1LL * pl - 1LL * G[i][pos1]);
if (pos2 < G[i].size()) rem = min(rem, 1LL * G[i][pos2] - 1LL * pr);
minx = min(minx, make_pair(rem, i));
}
totalcost += 2LL * minx.first;
pl = min(pl, cl[minx.second]);
pr = max(pr, cr[minx.second]);
}
for (int i = 0; i < n; i++) totalcost += 1LL * abs(p[i] - i);
return totalcost;
}
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:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos2 < G[i].size()) rem = min(rem, 1LL * G[i][pos2] - 1LL * pr);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
20 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
21 ms |
23780 KB |
Output is correct |
| 8 |
Correct |
21 ms |
23796 KB |
Output is correct |
| 9 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 13 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 15 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 16 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 17 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 18 |
Correct |
22 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
20 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
21 ms |
23780 KB |
Output is correct |
| 8 |
Correct |
21 ms |
23796 KB |
Output is correct |
| 9 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 13 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 15 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 16 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 17 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 18 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 19 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 21 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 22 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 23 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 24 |
Correct |
22 ms |
23964 KB |
Output is correct |
| 25 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 26 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 27 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 28 |
Correct |
21 ms |
23864 KB |
Output is correct |
| 29 |
Correct |
21 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
20 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
21 ms |
23780 KB |
Output is correct |
| 8 |
Correct |
21 ms |
23796 KB |
Output is correct |
| 9 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 13 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 15 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 16 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 17 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 18 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 19 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 21 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 22 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 23 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 24 |
Correct |
22 ms |
23964 KB |
Output is correct |
| 25 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 26 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 27 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 28 |
Correct |
21 ms |
23864 KB |
Output is correct |
| 29 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 30 |
Correct |
165 ms |
39688 KB |
Output is correct |
| 31 |
Correct |
168 ms |
39872 KB |
Output is correct |
| 32 |
Correct |
142 ms |
39800 KB |
Output is correct |
| 33 |
Correct |
159 ms |
39800 KB |
Output is correct |
| 34 |
Correct |
151 ms |
39672 KB |
Output is correct |
| 35 |
Correct |
156 ms |
39672 KB |
Output is correct |
| 36 |
Correct |
160 ms |
39800 KB |
Output is correct |
| 37 |
Correct |
166 ms |
39800 KB |
Output is correct |
| 38 |
Correct |
161 ms |
39672 KB |
Output is correct |
| 39 |
Correct |
159 ms |
39672 KB |
Output is correct |
| 40 |
Correct |
164 ms |
39720 KB |
Output is correct |
| 41 |
Correct |
167 ms |
39672 KB |
Output is correct |
| 42 |
Correct |
160 ms |
39672 KB |
Output is correct |
| 43 |
Correct |
152 ms |
39764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23808 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
20 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
21 ms |
23780 KB |
Output is correct |
| 8 |
Correct |
21 ms |
23796 KB |
Output is correct |
| 9 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 12 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 13 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 14 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 15 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 16 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 17 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 18 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 19 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 21 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 22 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 23 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 24 |
Correct |
22 ms |
23964 KB |
Output is correct |
| 25 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 26 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 27 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 28 |
Correct |
21 ms |
23864 KB |
Output is correct |
| 29 |
Correct |
21 ms |
23936 KB |
Output is correct |
| 30 |
Correct |
165 ms |
39688 KB |
Output is correct |
| 31 |
Correct |
168 ms |
39872 KB |
Output is correct |
| 32 |
Correct |
142 ms |
39800 KB |
Output is correct |
| 33 |
Correct |
159 ms |
39800 KB |
Output is correct |
| 34 |
Correct |
151 ms |
39672 KB |
Output is correct |
| 35 |
Correct |
156 ms |
39672 KB |
Output is correct |
| 36 |
Correct |
160 ms |
39800 KB |
Output is correct |
| 37 |
Correct |
166 ms |
39800 KB |
Output is correct |
| 38 |
Correct |
161 ms |
39672 KB |
Output is correct |
| 39 |
Correct |
159 ms |
39672 KB |
Output is correct |
| 40 |
Correct |
164 ms |
39720 KB |
Output is correct |
| 41 |
Correct |
167 ms |
39672 KB |
Output is correct |
| 42 |
Correct |
160 ms |
39672 KB |
Output is correct |
| 43 |
Correct |
152 ms |
39764 KB |
Output is correct |
| 44 |
Incorrect |
22 ms |
23808 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 45 |
Halted |
0 ms |
0 KB |
- |
