Submission #1012192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012192		hyakup	Ancient Books (IOI17_books)	C++17	50 / 100	120 ms	9232 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define ll long long

const ll maxn = 1e6 + 10;

bool marc[maxn];

long long minimum_walk(vector<int> p, int s) {
	if( is_sorted( p.begin(), p.end() ) ) return 0;
	ll n = (ll)p.size();
	ll resp = 0;
	for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i);
	ll maxi = -1;
	bool contido = false;
	for( ll i = 0; i < n; i++ ){
		if( !marc[i] && p[i] != i ){
			if( maxi != -1 && i > maxi ) resp += 2LL*(i - maxi);
			ll cur = i;
			while( !marc[cur] ){
				maxi = max( maxi, cur );
				marc[cur] = true;
				cur = p[cur];
			}
			if( i <= s && s <= maxi ) contido = true;
		}
	}
	if( contido ){
		ll desloc = 2*maxn;
		for( int i = 0; i < n; i++ ) if( marc[i] ) desloc = min( desloc, 2LL*abs(i - s));
		return resp + desloc;
	}
	bool ok = true;
	for( int i = s; i >= 0; i-- ) if( marc[i] ) ok = false;
	if( ok ){
		ll desloc = 2*maxn;
		for( int i = s; i < n; i++ ) if( marc[i] ) desloc = min( desloc, 2LL*abs(i - s));
		return resp + desloc;
	}
	ok = true;
	for( int i = s; i < n; i++ ) if( marc[i] ) ok = false;
	if( ok ){
		ll desloc = 2*maxn;
		for( int i = s; i >= 0; i-- ) if( marc[i] ) desloc = min( desloc, 2LL*abs(i - s));
		return resp + desloc;
	}
	return resp;
}

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