#include<bits/stdc++.h>
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "books.h"
#define ll long long
const int maxn = 1000100;
int par[maxn];
bool seen[maxn];
int getpar(int x){
if(par[x] < 0) return x;
return par[x] = getpar(par[x]);
}
long long minimum_walk(std::vector<int> p, int s) {
ll res = 0;
int n = p.size();
fill(par,par+n,-1);
for2(i,0,n) res += abs(i-p[i]);
for2(rep,0,n){
int i = (rep+s)%n;
if(seen[i]) continue;
int l = min(i,p[i]);
int r = max(i,p[i]);
bool SS = 0;
int L = i;
int R = i;
seen[i] = 1;
while(1){
int j = -1;
if(L != l){
L--;
j = L;
}
if(R != r){
R++;
j = R;
}
seen[j] = 1;
if( j == -1) break;
int x = getpar(i);
int y = getpar(j);
if(x == getpar(s) || y == getpar(s)) SS=1;
if(x != y){
if(par[x] < par[y]) swap(x,y);
par[y] += par[x];
par[x] = y;
}
}
if(SS && rep) res += 2;
}
for2(i,0,n) if(getpar(i) == i) res += 2;
res -= 2;
for(int i = n-1; i > s; i--){
if(par[getpar(i)] != -1) break;
res -= 2;
}
for2(i,0,n){
if(par[getpar(i)] != -1 || i == s) break;
res -= 2;
}
return res;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:39:10: warning: array subscript is below array bounds [-Warray-bounds]
seen[j] = 1;
~~~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
432 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
3 ms |
748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
748 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
432 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
3 ms |
748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
748 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
432 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
3 ms |
748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
748 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '4076' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
432 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
3 ms |
748 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
748 KB |
Output is correct |
| 12 |
Correct |
3 ms |
748 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 14 |
Halted |
0 ms |
0 KB |
- |
