#include "books.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll i,w;
bool operator<(const obj &o)const{
return w>o.w;
}
};
long long minimum_walk(std::vector<int> p, int s) {
ll ans = 0;
ll n = p.size();
/*
if (s == 0){
vector<ll> u(n,0);
for(ll i = 0;i<n;i++){
if(p[i]!=i){
ans += i-s;
s = i;
ll x = i;
do{
ans += abs(p[x]-x);
ll y = x;
x = p[x];
p[y] = y;
} while(x!=i);
}
}
ans += s;
}*/
ll gpc = 0;
vector<ll> gp(n,-1);
vector<ll> L,R;
vector<vector<ll>> gps;
for(ll i = 0;i<n;i++){
if (gp[i]==-1){
ll cur = gpc++;
gps.emplace_back();
L.push_back(n);
R.push_back(0);
ll x = i;
do{
L[cur] = min(x,L[cur]);
R[cur] = max(x,R[cur]);
gp[x] = cur;
gps[cur].push_back(x);
ans += abs(p[x]-x);
x = p[x];
} while(x!=i);
}
}/*
for(ll i = 0;i<gpc;i++){
cout << L[i] << "~" << R[i] << " " << gps[i].size() << endl;
}*/
vector<ll> cost(n,n);
priority_queue<obj> q;
q.push({s,0});
vector<ll> vis(gpc,0);
while(!q.empty()){
auto [i,w] = q.top();q.pop();
if (cost[i]<=w) continue;
cost[i] = w;
ll l = n,r = 0;
if (!vis[gp[i]]){
vis[gp[i]] = 1;
if (gps[gp[i]].size()>1) ans += cost[i]*2;
for(ll j : gps[gp[i]]){
q.push({j,0});
}
l = L[gp[i]];
r = R[gp[i]];
}
//cerr << i << " " << w << " " << l << " " << r << endl;
if(i>0) q.push({i-1,l<=i-1&&i-1<=r?0:w+1});
if(i<n-1) q.push({i+1,l<=i+1&&i+1<=r?0:w+1});
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
436 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
440 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
436 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
440 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338588' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
436 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
440 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338588' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3066' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
436 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
440 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338588' |
| 20 |
Halted |
0 ms |
0 KB |
- |
