#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
//#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN = 1000000;
//Global Variables
ll N, out = 0, loc[MAXN], comp[MAXN], at = 0;
/// element , element
pair<int, int> rng[MAXN];
/// comp
bool vis[MAXN], del[MAXN];
/// element , comp
void go1(int at, int co) {
if (comp[at] != -1) return;
rng[co].a = min(rng[co].a, at);
rng[co].b = max(rng[co].b, at);
comp[at] = co;
out += abs(loc[at]-at);
go1(loc[at], co);
}
void go(int at) {
if (vis[at]) return;
vis[at] = true;
go(loc[at]);
}
ll minimum_walk(vector<int> p, int s) {
N = p.size();
ffi {rng[i] = mp(N, -1); comp[i] = -1; loc[i] = p[i];}
ffi if (comp[i] == -1) {
go1(i, at);
at++;
}
//w<< "from components: " << out<<e;
sort(rng, rng+at);
int far = -1;
For (i, 0, at) if (rng[i].a >= s) {
if (rng[i].a < far) {
//w<<"deleting"<<e;
del[comp[rng[i].a]] = true;
}
far = max(far, rng[i].b);
}
//ffi w<< i c del[comp[i]]<<e;
far = N+1;
for (int i=at-1; i>=0; i--) if (rng[i].b <= s) {
if (rng[i].b > far) {
//w<<"deleting"<<e;
del[comp[rng[i].a]] = true;
}
far = min(far, rng[i].a);
}
//ffi w<< i c del[comp[i]]<<e;
ffi if (loc[i] == i) del[comp[i]] = true;
bool moved = false;
far = s;
if (!del[comp[s]]) far = rng[comp[s]].b;
For (i, 0, at) if (rng[i].a >= s) {
if (!del[comp[rng[i].a]]) {
out += 2*(rng[i].a - far);
moved = true;
}
if (loc[rng[i].b] != rng[i].b) far = max(far, rng[i].b);
//w<< out<<e;
}
far = s;
if (!del[comp[s]]) far = rng[comp[s]].a;
for (int i=at-1; i>=0; i--) if (rng[i].b <= s) {
if (!del[comp[rng[i].a]]) {
out += 2*(far - rng[i].b);
moved = true;
}
if (loc[rng[i].b] != rng[i].b) far = min(far, rng[i].a);
//w<< out<<e;
}
//w<< "moved: " << moved c out<<e;
if (moved) return out;
/// find closest location to s that isn't deleted
int dist = N+1;
ffi if (!del[comp[i]]) {
dist = min(dist, abs(s-i));
}
if (dist == N+1) dist = 0;
return out + 2*dist;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '8', found: '2' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '8', found: '2' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '8', found: '2' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3950' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '8', found: '2' |
| 4 |
Halted |
0 ms |
0 KB |
- |
