Submission #51061

#	Time	Username	Problem	Language	Result	Execution time	Memory
51061		FLDutchman	Ancient Books (IOI17_books)	C++14	50 / 100	510 ms	94572 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = l; i < r; i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

const ll NMAX = 1e6 + 10;
const ll INF = 1e9;

vi cycles[NMAX];
ll numCycles, N, S;
vi vis;
vi point;

void flood(ll n, ll c){
	//cout << "Flood " << n << " " << c << endl;
	cycles[c].pb(n);
	ll k = point[n];
	vis[n] = c;
	if(vis[k] == -1) flood(k, c); 
}

ii bounds[NMAX];
// 
/*ii bounds(ll p, ll c){
	//cout << p << endl;
	auto &cy = cycles[c];	
	if(cy[0] > p) return {-1, cy[0]};
	if(cy.back() <= p) return {cy.back(), INF};
	auto x = lower_bound(cycles[c].begin(), cycles[c].end(), p);
	return {*x, *(++x)};
}*/

ll f(ll lbound, ll rbound){
	rbound --;
	ii &k = bounds[vis[lbound]];
	ll lgoal = k.fst, rgoal = k.snd;
	//cout << lgoal << " " << rgoal << endl;
	ll l = lbound, r = rbound;
	while(l < lgoal || r > rgoal){
		//cout << l << " " << r << endl;
		ll t;
		if(l >= lgoal) t = r--;
		else t = l++;
		ii &k = bounds[vis[t]];
		lgoal = max(lgoal, k.fst);
		rgoal = min(rgoal, k.snd);
	}
	//cout << lgoal << " " << rgoal << endl;
	if(lgoal == S) return 0;
	ll li = S, ri = S+1;
	ll lm = lgoal, rm = lgoal;

	ll c1 = 0;
	FOR(i, lgoal+1, S+1){
		ll a = cycles[vis[i]][0], b = cycles[vis[i]].back()+1;
		if(a != i) continue;
		if(b >= S) {
			li = i;
			break;
		} 
		if(rm <= i){
			if(rm - lm > 1) c1 += lm - rm;
			lm = i;
		}
		rm = max(rm, b);
	}
	c1 += li - lgoal;

	// closed interval
	lm = rgoal-1; rm = rgoal-1;
	ll c2 = 0;
	for(int i = rgoal-1; i > S; i--){
		ll a = cycles[vis[i]][0], b = cycles[vis[i]].back();
		if(b != i) continue;
		if(a <= S){
			ri = i+1;
			break;
		}
		if(i < lm){
			if(rm - lm > 1) c2 += lm - (rm + 1);
			rm = i;
		}
		lm = min(lm, a);
	}
	c2 += rgoal+1 - ri;
	// Interval covering 
	//cout << "cover " <<  li << " " << ri << endl;
	//cout << "c1 c2: " << c1 << " " << c2 << endl;
	ll res = f(li, ri);


	return res + min(c1, c2);	
}

long long minimum_walk(std::vector<int> p, int s) {
	vis.assign(p.size(), -1);
	N = p.size();
	S = s;
	FOR(i, 0, N) point.pb(p[i]);
	FOR(i, 0, N) if(vis[i] == -1) flood(i, numCycles++);
	FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
	FOR(c, 0, numCycles) {
		auto &cy = cycles[c];	
		if(cy[0] > s) bounds[c] = {-1, cy[0]};
		else if(cy.back() <= s) bounds[c] = {cy.back(), INF};
		else {
			auto x = upper_bound(cycles[c].begin(), cycles[c].end(), s);
			bounds[c] = {*(x-1), *(x)};
		}
		//cout << c << ": " << bounds[c].fst << " " << bounds[c].snd << endl;
	}

	//cout << "Preprocessed" << endl;
	//ii k = bounds(2, 1);
	//cout << k.fst << " " << k.snd << endl;
	//Find segments:
	vii segs;
	ll rm = 0;
	ll lm = 0;
	ll l = -1, r = -1;
	//cout << "numCycles: " << numCycles << endl;
	//FOR(i, 0, numCycles) {
		//for(int k : cycles[i]) cout << k << " ";
		//cout << endl;
	//}
	FOR(i, 0, numCycles){
		if(cycles[i].size() == 1) continue;
		if(rm <= cycles[i][0]) {
			if(rm - lm > 1) segs.pb({lm, rm});
			if(lm <= S and S < rm) l = lm, r = rm;
			lm = cycles[i][0]; rm = cycles[i].back()+1;
		}
		rm = max(rm, cycles[i].back()+1);
		//cout << lm << " " << rm << " " << i << endl;
	}

	if(rm - lm > 1) segs.pb({lm, rm});

	//cout << segs.size() << endl;
	ll dist = 0;
	//cout << dist << endl;
	FOR(i, 0, N) dist += abs(i - p[i]);
	//cout << dist << endl;
	//cout << segs.size() - 1 << endl;
	//FOR(i, 0, (ll)segs.size()) cout << segs[i].fst << " " << segs[i].snd << endl;
	FOR(i, 0, (ll)segs.size()-1){
		dist += 2*(segs[i+1].fst - (segs[i].snd-1) );
	}
	if(segs.size() > 0){
		if(segs[0].fst > S) dist += 2 * (segs[0].fst - S);
		if(segs.back().snd <= S) dist += 2*(S - segs.back().snd+1);
	}
	
	//cout << "sfdf" << endl;
	if(l != -1) dist += 2*f(l, r);
	return dist;
}
/*
3 1
0 2 1

4 0
0 1 3 2

4 1
2 3 0 1
4 0
0 1 2 3

10 4
0 1 4 5 2 3 7 6 9 8
10 4
0 6 4 5 2 3 7 1 9 8
10 4
0 6 2 5 4 3 7 1 9 8
10 0
0 6 2 5 4 3 7 1 9 8
*/

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