Submission #1222092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222092		HappyCapybara	Ancient Books (IOI17_books)	C++17	100 / 100	254 ms	20044 KiB

books

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

#define ll long long

ll minimum_walk(vector<int> p, int s){
	int n = p.size();
	int li = s, ri = s;
	for (int i=0; i<s; i++){
		if (p[i] != i){ li = i; break; }
	}
	for (int i=n-1; i>s; i--){
		if (p[i] != i){ ri = i; break; }
	}
	s -= li;
	vector<int> np;
	for (int i=li; i<=ri; i++) np.push_back(p[i]-li);
	p = np;
	n = p.size();
	vector<int> cl(n, -1), cr(n, -1);
	ll res = 0;
	for (int i=0; i<n; i++){
		if (cl[i] != -1) continue;
		int lm = i, rm = i;
		int cur = i;
		while (cl[cur] == -1){
			lm = min(lm, cur);
			rm = max(rm, cur);
			cl[cur] = -2;
			res += abs(p[cur]-cur);
			cur = p[cur];
		}
		while (cl[cur] == -2){
			cl[cur] = lm;
			cr[cur] = rm;
			cur = p[cur];
		}
	}
	int l = s, r = s, pl = cl[s], pr = cr[s];
	bool done = false;
	while (l != 0 || r != n-1){
		while (l != pl || r != pr){
			if (l != pl){
				l--;
				pl = min(pl, cl[l]);
				pr = max(pr, cr[l]);
			}
			if (r != pr){
				r++;
				pl = min(pl, cl[r]);
				pr = max(pr, cr[r]);
			}
		}
		if ((l == 0 || done) && r != n-1){
			res += 2;
			r++;
			pl = min(pl, cl[r]);
			pr = max(pr, cr[r]);
		}
		if ((r == n-1 || done) && l != 0){
			res += 2;
			l--;
			pl = min(pl, cl[l]);
			pr = max(pr, cr[l]);
		}
		if (!done && l != 0 && r != n-1){
			bool found = false;
			for (int i=l-1; i>=0; i--){
				if (cr[i] > r){ found = true; break; }
			}
			if (!found){ done = true; continue; }
			int glc = 0, gll = l, glpl = pl, glpr = pr, grc = 0, grr = r, grpl = pl, grpr = pr;
			while (glpr == pr){
				if (glpl == gll) glc += 2;
				gll--;
				glpl = min(glpl, cl[gll]);
				glpr = max(glpr, cr[gll]);
			}
			while (grpl == pl){
				if (grpr == grr) grc += 2;
				grr++;
				grpl = min(grpl, cl[grr]);
				grpr = max(grpr, cr[grr]);
			}
			if (glc < grc){
				res += glc;
				l = gll;
				pl = glpl;
				pr = glpr;
			}
			else {
				res += grc;
				r = grr;
				pl = grpl;
				pr = grpr;
			}
		}
	}
	return res;
}

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