Submission #423870

#	Time	Username	Problem	Language	Result	Execution time	Memory
423870		Rudy420	고대 책들 (IOI17_books)	C++17	100 / 100	216 ms	24656 KiB

books

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "books.h"

long long minimum_walk(vector<int> p, int s) {
	long long sum = 0;
	int L = -1,R = -1;
	int n = sz(p);
	for(int i=0;i<n;i++) sum += abs(i - p[i]);
	for(int i=0;i<n;i++){
		if(p[i]!=i){
			L = i;
			break;
		}
	}
	if(L == -1) return 0;
	for(int i=n-1;i>=0;i--){
		if(p[i]!=i){
			R = i;
			break;
		}
	}
	L = min(L, s);
	R = max(R, s);
	vector<int> v(n, 0);
	int l=s,r=s;
	queue<int> q;
	q.push(s);
	long long ans = 0;
	while(l != L || r != R){
		while(q.size()){
			int i = q.front();
			q.pop();
			if(!v[i]){
				int ln=i,rn=i;
				v[i] = 1;
				int j = p[i];
				while(j != i){
					v[j] = 1;
					ln = min(ln, j);
					rn = max(rn, j);
					j = p[j];
				}
				for(int j=ln;j<l;j++) q.push(j);
				for(int j=r+1;j<=rn;j++) q.push(j);
				l = min(l, ln); r = max(r, rn);
			}
		}

		long long cl = 0, cr = 0;
		vector<int> qL, qR;
		int sl = -1, sr = -1;
		int oldl = l, oldr = r;
		while(l != L){
			l--;
			q.push(l);
			cl += 2;
			while(q.size()){
				int i = q.front();
				q.pop();
				if(!v[i]){
					int ln=i,rn=i;
					v[i] = 1;
					qL.push_back(i);
					int j = p[i];
					while(j != i){
						v[j] = 1;
						qL.push_back(j);
						ln = min(ln, j);
						rn = max(rn, j);
						j = p[j];
					}

					if(rn > r){
						sl = i;
						break;
					}

					for(int j=ln;j<l;j++) q.push(j);
					for(int j=r+1;j<=rn;j++) q.push(j);
					l = min(l, ln); r = max(r, rn);
				}
			}
			if(sl != -1) break;
		}

		for(int i : qL) v[i] = 0;
		while(sz(q)) q.pop();
		l = oldl; r = oldr;
		while(r != R){
			r++;
			q.push(r);
			cr += 2;
			while(q.size()){
				int i = q.front();
				q.pop();
				if(!v[i]){
					int ln=i,rn=i;
					v[i] = 1;
					qR.push_back(i);
					int j = p[i];
					while(j != i){
						v[j] = 1;
						qR.push_back(j);
						ln = min(ln, j);
						rn = max(rn, j);
						j = p[j];
					}

					if(ln < l){
						sr = i;
						break;
					}

					for(int j=ln;j<l;j++) q.push(j);
					for(int j=r+1;j<=rn;j++) q.push(j);
					l = min(l, ln); r = max(r, rn);
				}
			}
			if(sr != -1) break;
		}

		for(int i : qR) v[i] = 0;
		while(sz(q)) q.pop();
		l = oldl; r = oldr;

		if(sl == -1){
			ans += cl + cr;
			break;
		}
		else{
			if(cl < cr) ans += cl, q.push(sl);
			else ans += cr, q.push(sr);
		}

	}

	return ans + sum;
}

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