#include "books.h"
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxN = 1'000'000;
const int ind_R = 1'000'005;
const int ind_L = -1;
const long long INF = 1'000'000'000'000'000'000LL;
int N;
vector<int> P;
int S;
int cycle_ind = -1;
vector<int> cycle(maxN, -1);
vector<int> L(maxN, ind_R);
vector<int> R(maxN, ind_L);
long long essential_cost = 0;
void extend(int& l, int& r) //[l, r] is extended fully except for the cycles of l and r
{
int l_new = min(L[cycle[l]], L[cycle[r]]);
int r_new = max(R[cycle[l]], R[cycle[r]]);
// cerr << "ln = " << l_new << ", rn = " << r_new << '\n';
while(l_new <= l-1 || r+1 <= r_new)
{
if(l_new <= l-1)
{
l--;
l_new = min(l_new, L[cycle[l]]);
r_new = max(r_new, R[cycle[l]]);
}
if(r+1 <= r_new)
{
r++;
l_new = min(l_new, L[cycle[r]]);
r_new = max(r_new, R[cycle[r]]);
}
}
}
long long minimum_walk(vector<int> p, int s)
{
N = p.size();
P = p;
S = s;
int solve_L = S;
int solve_R = S;
for(int i = 0; i < N; i++)
{
essential_cost += abs(P[i] - i);
if(P[i] != i)
{
solve_L = min(solve_L, i);
solve_R = max(solve_R, i);
}
if(cycle[i] != -1) continue;
cycle_ind++;
int j = i;
do
{
cycle[j] = cycle_ind;
L[ cycle[j] ] = min(L[ cycle[j] ], j);
R[ cycle[j] ] = max(R[ cycle[j] ], j);
j = P[j];
} while(j != i);
}
if(solve_L == S && solve_R == S) return 0;
// for(int i = 0; i < N; i++) cerr << cycle[i] << ' ';
// cerr << '\n';
//
// cerr << "solve range = " << solve_L << ' ' << solve_R << '\n';
long long extra_cost = 0;
int l = S;
int r = S;
// cerr << "l = " << l << ", r = " << r << '\n';
extend(l, r);
// cerr << "l = " << l << ", r = " << r << '\n';
long long dp[1000][1000];
dp[solve_L][solve_R] = 0;
for(int delta = solve_R - solve_L; delta >= 0; delta--)
{
for(int lx = solve_L; lx + delta <= solve_R; lx++)
{
int rx = lx + delta;
if(lx == solve_L && rx == solve_R)
{
dp[lx][rx] = 0;
continue;
}
dp[lx][rx] = INF;
int l, r;
l = lx-1;
r = rx;
if(solve_L <= l)
{
extend(l, r);
dp[lx][rx] = min(dp[lx][rx], dp[l][r] + 2);
}
l = lx;
r = rx+1;
if(r <= solve_R)
{
extend(l, r);
dp[lx][rx] = min(dp[lx][rx], dp[l][r] + 2);
}
}
}
// while(l != solve_L || r != solve_R)
// {
// extend(l, r);
//
// int new_l = -1, new_r = -1;
// int left_cost, right_cost;
// for(int i = l-1; i >= solve_L; i--)
// {
// if(P[i] != i)
// {
// new_l = i;
// left_cost = 2*(l - new_l);
// break;
// }
// }
// for(int i = r+1; i <= solve_R; i++)
// {
// if(P[i] != i)
// {
// new_r = i;
// right_cost = 2*(new_r - r);
// break;
// }
// }
//
// if(new_l != -1 && new_r != -1)
// {
// int l1 = l, r1 = r;
// extend(new_l, r1);
// extend(l1, new_r);
//
// // if((S <= R[ cycle[new_l] ]) != (L[ cycle[new_r] ] <= S))
// // while(1);
//
// if(S <= r1) //&& L[ cycle[new_r] ] <= S
// {
// extra_cost += min(left_cost, right_cost);
// }
// else
// {
// extra_cost += left_cost + right_cost;
// }
//
// l = new_l;
// r = new_r;
// extend(l, r);
// }
// else if(new_l != -1)
// {
// extra_cost += left_cost;
// l = new_l;
// extend(l, r);
// }
// else if(new_r != -1)
// {
// extra_cost += right_cost;
// r = new_r;
// extend(l, r);
// }
// else break;
// }
return essential_cost + dp[S][S];
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:95:12: warning: unused variable 'extra_cost' [-Wunused-variable]
95 | long long extra_cost = 0;
| ^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19788 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19860 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19788 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19788 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19860 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19788 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19788 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19860 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19788 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
19860 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3306' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19788 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19860 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19788 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
