Submission #138489

#	Time	Username	Problem	Language	Result	Execution time	Memory
138489		almogwald	Ancient Books (IOI17_books)	C++14	0 / 100	2 ms	376 KiB

books

#include <utility>
#include <algorithm>
#include <math.h>
#include "books.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define maxl 10000000000
typedef long long lol;
using namespace std;

long long minimum_walk(vector<int> p, int s) {
	int n=p.size();
	vector<int> a(n,-1);
	lol sum=0;
	int cur=s;
	do{
		sum+=abs(p[cur]-cur);
		cur= p[cur];
		a[cur]=0;
	}while(cur !=s);
	int num=1;
	vector<int> b(n+1,s);
	fori(i,n){
		if(p[i]==i||a[i]!=-1){
			continue;
		}
		int l=-10000000;
		int r=n;
		int cur=i;
		do{
			if(cur<s){
				l=max(l,cur);
			}else{
				r=min(r,cur);
			}
			sum+=abs(p[cur]-cur);
			cur= p[cur];
			a[cur]=num;
		}while(cur !=i);
		num++;
		b[r-1]=l;
	}
	int l=s;
	int mon=n;
	forib(i,n){
		if(i<s){
			break;
		}
		l=min(l,b[i]);
		mon=min(mon,i-s+s-l);
	}
	return sum+mon*2;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30