Submission #109654

#	Time	Username	Problem	Language	Result	Execution time	Memory
109654		Kepperoni	Ancient Books (IOI17_books)	C++14	50 / 100	276 ms	40660 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll MAXN = 1e6 + 10;

vector<pii> pi;
bool vis[MAXN];
ll n;
ll ans;
bool done[MAXN];
ll nr[MAXN], nl[MAXN];

long long minimum_walk(std::vector<int> p, int s) {
	n = p.size();
	for(int i=0; i<n; i++){
		ans += abs(i - p[i]);
		//cout << i << " " << p[i] << endl;
	}

	for(int i=0; i<n; i++){
		if(!vis[i]){
			ll cl = i, cr = i;
			ll cu = i;
			while(!vis[cu]){
				cl = min(cu, cl);
				cr = max(cu, cr);
				vis[cu] = 1;
				cu = p[cu];
			}
			pi.pb({cl, cr});
		}
	}

	for(int i=0; i<n; i++) nr[i] = nl[i] = -1;

	//cout << ans << endl;

	ll lar = s, fil = s;
	ll cl = s, cr = s;
	for(int i=0; i<pi.size(); i++){
		if(pi[i].x <= s && s <= pi[i].y){
			cl = min(cl, pi[i].x);
			cr = max(cr, pi[i].y);
		}

		nr[pi[i].x] = pi[i].y;
		nl[pi[i].y] = pi[i].x;

		if(pi[i].x != pi[i].y){
			lar = max(lar, pi[i].y);
			fil = min(fil, pi[i].x);
		}
	}

	//cout << fil << " " << lar << endl;

	for(int i=s; i<=lar; i++){
		if(i > cr){
			ans += 2;
			cr++;
		}

		if(nr[i] != -1)
			cr = max(cr, nr[i]);
	}

	for(int i=s; i>=fil; i--){
		if(i < cl){
			ans += 2;
			cl--;
		}

		if(nl[i] != -1)
			cl = min(cl, nl[i]);
	}

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<pi.size(); i++){
               ~^~~~~~~~~~

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