Submission #1222087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222087		HappyCapybara	Ancient Books (IOI17_books)	C++17	50 / 100	187 ms	19884 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];
	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 (r != n-1){
			res += 2;
			r++;
			pl = min(pl, cl[r]);
			pr = max(pr, cr[r]);
		}
	}
	return res;
}

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