| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 117900 | sealnot123 | Ancient Books (IOI17_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1000007;
int n;
int mk[N];
vector<PII> inter,interx;
long long minimum_walk(vector<int> p, int s) {
int a,b,c,d,i,j,k;
int l,r;
LL ans = 0;
n = SZ(p);
if(n==1) return 0;
for(i=0;i<n;i++){
if(p[i]==i || mk[i]) continue;
l = r = i;
mk[i] = 1;
a = p[i];
ans += abs(i-p[i]);
while(a!=i){
mk[a] = 1;
ans += abs(a-p[a]);
l = min(l, a);
r = max(r, a);
a = p[a];
}
inter.pb({l,r});
}
sort(inter.begin(),inter.end());
l = r = -1;
for(PII it : inter){
if(it.x > r){
if(r!=-1) interx.pb({l,r});
l = it.x;
}
r = max(r, it.y);
}
if(l!=-1) interx.pb({l,r});
for(i=0;i<SZ(interx);i++){
PII it1 = interx[i];
// printf("%d %d\n",it1.x,it1.y);
if(it1.x<=s && it1.y>=s){
assert(0);
int tmp = 1<<30;
for(j=s;j>=0;j--){
if(mk[j]){
tmp = min(tmp,s-j); break;
}
}
for(j=s;j<n;j++){
if(mk[j]){
tmp = min(tmp,j-s); break;
}
}
ans += 2*tmp;
}
if(i+1==SZ(interx)) continue;
PII it2 = interx[i+1];
ans += 2*(it2.x-it1.y);
}
if(!interx.empty()){
if(s<interx[0].x) ans += 2*(interx[0].x-s);
if(s>interx.back().y) ans += 2*(s-interx.back().y);
}
return ans;
}
/*
7 4
1 0 6 5 4 2 3
8 4
7 1 2 0 3 5 6 4
8 4
7 5 6 0 3 2 1 4
5 2
3 4 2 0 1
*/