#include "books.h"
#include "bits/stdc++.h"
using namespace std;
int col[1000010];
bool vis[1000010];
bool v[1000010];
int l[1000010], r[1000010];
int cmp[1000010];
void dfs(int x, int c) {
v[x] = true;
for(int i = l[x]; i <= r[x]; i++) {
cmp[i] = c;
if(col[i] != -1 && v[col[i]] == false) {
dfs(col[i], c);
}
}
}
long long minimum_walk(std::vector<int> p, int s) {
long long ans = 0;
int n = p.size();
for(int i = 0; i < n-1; i++) {
int go_left = 0;
int go_right = 0;
for(int j = 0; j <= i; j++) {
if(p[j] > i) {
++go_left;
}
}
for(int j = i + 1; j < n; j++) {
if(p[j] < i+1) {
++go_right;
}
}
assert(go_left == go_right);
ans += go_left + go_right;
}
memset(col, -1, sizeof col);
memset(v, false, sizeof v);
int id = 0;
for(int i = 0; i < n; i++) {
if(col[i] != -1 || p[i] == i) continue;
int cur = i;
++id;
l[id] = n;
r[id] = 0;
while(col[cur] == -1) {
l[id] = min(l[id], cur);
r[id] = max(r[id], cur);
col[cur] = id;
cur = p[cur];
}
}
memset(cmp, -1, sizeof cmp);
int c = 0;
for(int i = 0; i < n; i++) {
if(col[i] != -1 && v[col[i]] == false) {
dfs(col[i], ++c);
}
}
for(int i = 0; i < n; i++) {
col[i] = cmp[i];
}
int p1 = 0;
int p2 = n-1;
while(col[p1] == -1 && p1 < s) {
++p1;
}
while(col[p2] == -1 && p2 > s) {
--p2;
}
for(int i = p1; i < p2; i++) {
if(col[i] != col[i + 1] || col[i] == -1 || col[i + 1] == -1) {
ans += 2;
}
}
return ans;
}
// 30 0
// 17 28 26 18 29 8 23 9 22 20 16 3 7 24 5 19 4 2 11 25 0 14 6 13 1 12 21 27 15 10
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9208 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 13 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9208 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 13 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 20 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 21 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 22 |
Correct |
13 ms |
9424 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9428 KB |
Output is correct |
| 24 |
Correct |
11 ms |
9552 KB |
Output is correct |
| 25 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 26 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 27 |
Correct |
14 ms |
9552 KB |
Output is correct |
| 28 |
Correct |
10 ms |
9552 KB |
Output is correct |
| 29 |
Correct |
13 ms |
9552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9208 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 13 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 20 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 21 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 22 |
Correct |
13 ms |
9424 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9428 KB |
Output is correct |
| 24 |
Correct |
11 ms |
9552 KB |
Output is correct |
| 25 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 26 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 27 |
Correct |
14 ms |
9552 KB |
Output is correct |
| 28 |
Correct |
10 ms |
9552 KB |
Output is correct |
| 29 |
Correct |
13 ms |
9552 KB |
Output is correct |
| 30 |
Execution timed out |
2070 ms |
15256 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16092 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9208 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
9388 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 11 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 12 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 13 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 14 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 15 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 16 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 17 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9424 KB |
Output is correct |
| 19 |
Correct |
12 ms |
9424 KB |
Output is correct |
| 20 |
Correct |
10 ms |
9424 KB |
Output is correct |
| 21 |
Correct |
11 ms |
9424 KB |
Output is correct |
| 22 |
Correct |
13 ms |
9424 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9428 KB |
Output is correct |
| 24 |
Correct |
11 ms |
9552 KB |
Output is correct |
| 25 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 26 |
Correct |
12 ms |
9552 KB |
Output is correct |
| 27 |
Correct |
14 ms |
9552 KB |
Output is correct |
| 28 |
Correct |
10 ms |
9552 KB |
Output is correct |
| 29 |
Correct |
13 ms |
9552 KB |
Output is correct |
| 30 |
Execution timed out |
2070 ms |
15256 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
