#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> cycle;
vector<int> p;
ll n;
ll minc = 1e9;
ll maxc = -1e9;
ll findcycle(ll i, ll ptr){
cycle[i] = ptr;
minc=min(minc,i);
maxc=max(maxc,i);
if (cycle[p[i]]!=-1){
return abs(i-p[i]);
} else {
return abs(i-p[i]) + findcycle(p[i], ptr);
}
}
ll minimum_walk(std::vector<int> px, int s) {
p = px;
n = p.size();
cycle.resize(n,-1);
ll cycledist = 0;
ll ptr = 0;
vector<ll> cyclewidth(n+1);
for (ll i = 0; i<n; i++){
if (cycle[i]!=-1){continue;}
minc=1e9;maxc=-1e9;
ll dist = findcycle(i,ptr);
cyclewidth[minc]++;
cyclewidth[maxc]--;
cycledist+=dist;
ptr++;
}
//cout<<cycledist<<endl;
ll prev = 0;
bool iszero = true;
ll ctr = 0;
ll minabove=1e9;
ll maxbelow=-1e9;
//bool isbetween = false;
for (ll i = 0; i<=n; i++){
ctr+=cyclewidth[i];
/*if (ctr==0&&i==s){
isbetween=true;
}*/
if (iszero&&ctr>0){
if (i<=s){
maxbelow=max(maxbelow,i);
}
if (i>=s){
minabove=min(minabove,i);
}
if (prev!=0){cycledist+=2*(i-prev);}
iszero = false;
} else if ((!iszero)&&ctr==0){
if (i-1<=s){
maxbelow=max(maxbelow,i-1);
}
if (i-1>=s){
minabove=min(minabove,i-1);
}
prev = i;
iszero = true;
}
}
//cout<<maxbelow<<' '<<minabove<<endl;
//if (!isbetween){
cycledist+=2*(min(abs(minabove-s),abs(s-maxbelow)));
//}
return cycledist;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000000' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000000' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000000' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3594' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
0 ms |
256 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000000' |
| 10 |
Halted |
0 ms |
0 KB |
- |
