Submission #73439

#	Time	Username	Problem	Language	Result	Execution time	Memory
73439		SmsS	Ancient Books (IOI17_books)	C++14	0 / 100	3 ms	544 KiB

books

#include<bits/stdc++.h>
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "books.h"
#define ll long long
long long minimum_walk(std::vector<int> p, int s) {
//	if(s != 0) return 0;
	ll res = 0;
	int n = p.size();
	for2(i,0,n) res += abs(i-p[i]);
	vector<int> cmp(n,-1);
	vector<int> sz(n,-1);
	int cnt = 0;
	for2(i,0,n) if(cmp[i] == -1){
		int l = min(i,p[i]);
		int r = max(i,p[i]);
		int L = i;
		int R = i;
		while(L != l || R != r){
			while(l < L){
				L--;
				l = min(l,p[L]);
				r = max(r,p[L]);
			}
			while(R < r){
				R++;
				l = min(l,p[R]);
				r = max(r,p[R]);
			}

		}
		for2(i,l,r+1){
			sz[i] = r-l+1;
			cmp[i] = cnt;
		}
		cnt++;
		res += 2;
	}
//	for2(i,0,n) cout << cmp[i] << ' ';
//	cout << endl;
	res -= 2;
/*	for(int i = n-1; i > s; i--){
		if(sz[i] != 1) break;
		res -= 2;
	}
	for2(i,0,n){
		if(sz[i] != 1 || i == s) break;
		res -= 2;
	}*/
	return res;
}

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