Submission #521327

#	Time	Username	Problem	Language	Result	Execution time	Memory
521327		ymm	Ancient Books (IOI17_books)	C++17	100 / 100	683 ms	77672 KiB

books

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#include "books.h"

const int N = 1'000'010;
int col[N]; int cnt=0;
int mn[N], mx[N];

ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	fill(col,col+N,-1);
	fill(mn,mn+N,N);
	fill(mx,mx+N,0);
	cnt=0;
	Loop(i,0,n){
		if(col[i]<0){
			int j = i;
			while(col[j]<0){
				mn[cnt] = min(mn[cnt], j);
				mx[cnt] = max(mx[cnt], j);
				col[j] = cnt;
				j = p[j];
			}
			++cnt;
		}
	}
	int l=0, r=n-1;
	while(l<s && p[l]==l) ++l;
	while(r>s && p[r]==r) --r;
//	Loop(i,0,n) cout << col[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mx[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mn[i] << ' '; cout << '\n';
	int droot=0;
	// bfs
	{
		vector<int> dis(n, N);
		set<int> cand; Loop(i,l,r+1) cand.insert(i);
		deque<pii> q; q.emplace_back(col[s], 0); dis[col[s]]=0;
		while(q.size()){
			auto [v, d] = q.front(); q.pop_front();
			if(d != dis[v]) continue;
			int mn = ::mn[v], mx = ::mx[v];
			if(mn<=s&&s<=mx) droot=d;
			for(;;){
				int i;
				auto it = cand.lower_bound(mn);
				if(it == cand.end() || (i = *it) > mx) break;
//				cout<<i<<"!\n";
				cand.erase(it);
				if(d < dis[i = col[i]]){
					dis[i] = d;
					q.emplace_front(i, d);
				}
			}
			if(l<mn && d+1<dis[col[mn-1]]){
				dis[col[mn-1]] = d+1;
				q.emplace_back(col[mn-1], d+1);
			}
			if(mx<r && d+1<dis[col[mx+1]]){
				dis[col[mx+1]] = d+1;
				q.emplace_back(col[mx+1], d+1);
			}
		}
	}
//	cout << mnrt << ' ' << mxrt << ' ' << droot << '\n';
	ll ans = 0;
	Loop(i,l,r+1) ans += abs(i-p[i]);
	int foo=0;
	Loop(i,l,r+1) {
		droot += s<i && !foo;
		foo += i==mn[col[i]];
		foo -= i==mx[col[i]];
	}
	foo=0;
	LoopR(i,l,r+1){
		droot += i<s && !foo;
		foo += i==mx[col[i]];
		foo -= i==mn[col[i]];
	}
	return ans+2*droot;
}

//int main()
//{
//	/*vector<int> p = {0, 1, 2, 3};
//	do{
//		if(minimum_walk(p,0)==8){
//			for(int x : p) cout << x << ' ';
//			cout << '\n';
//		}
//	}while(next_permutation(p.begin(), p.end()));*/
//	cout << minimum_walk({5, 1, 2, 3, 4, 0}, 3) << '\n';
//}

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