Submission #797014

#	Time	Username	Problem	Language	Result	Execution time	Memory
797014		QwertyPi	Ancient Books (IOI17_books)	C++14	50 / 100	150 ms	29552 KiB

books

#include "books.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 1e6 + 11;
 
struct range{
	int l, r;
	bool extend(range rg){
		bool changed = false;
		if(rg.l < l) changed = true, l = rg.l;
		if(rg.r > r) changed = true, r = rg.r;
		return changed;
	}
	friend range operator+ (const range& s, const range& t){
		return {min(s.l, t.l), max(s.r, t.r)};
	}
	friend void operator+= (range& s, const range& t){
		s = s + t;
	}
	friend bool operator!= (const range& s, const range& t){
		return s.l != t.l || s.r != t.r;
	}
};
 
bool vis[MAXN];
range cyc[MAXN];
int dp[MAXN];
 
long long minimum_walk(vector<int> p, int s) {
	int n = p.size(); 
	
	bool all_eq = true; 
	for(int i = 0; i < n; i++) if(p[i] != i) all_eq = false;
	if(all_eq) return 0;
	
	int al = 0, ar = n - 1; while(p[al] == al) al++; while(p[ar] == ar) ar--;
	long long ans = 0;
	for(int i = 0; i < n; i++){
		ans += abs(p[i] - i);
	}
	
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			vector<int> c = {i}; int x = p[i]; range r = {i, i};
			while(x != c[0]){
				r.extend({x, x});
				c.push_back(x); 
				vis[x] = true; 
				x = p[x];
			}
			for(auto j : c) cyc[j] = r;
		}
	}
	
	for(int i = s - 1; i >= 0; i--){
		cyc[i].extend(cyc[i + 1]);
	}
	
	for(int i = s + 1; i < n; i++){
		cyc[i].extend(cyc[i - 1]);
	}
	
	{
		range cur = cyc[s], nxt = cyc[s];
		do{
			cur = nxt;
			nxt.extend(cyc[nxt.l]);
			nxt.extend(cyc[nxt.r]);
		}while(cur != nxt);
		cyc[s] = nxt;
	}
	for(int i = s - 1; i >= 0; i--){
		cyc[i].extend(cyc[i + 1]);
		range cur = cyc[i], nxt = cyc[i];
		do{
			cur = nxt;
			nxt.extend(cyc[nxt.l]);
			nxt.extend(cyc[nxt.r]);
		}while(cur != nxt);
		cyc[i] = nxt;
	}
	for(int i = s + 1; i < n; i++){
		cyc[i].extend(cyc[i - 1]);
		range cur = cyc[i], nxt = cyc[i];
		do{
			cur = nxt;
			nxt.extend(cyc[nxt.l]);
			nxt.extend(cyc[nxt.r]);
		}while(cur != nxt);
		cyc[i] = nxt;
	}
	
	range cur {s, s}; dp[s] = 0; int res = 1;
	while(cur.l > al || cur.r < ar){
		range nxt {s, s};
		if(cur.l > al) nxt += cyc[cur.l - 1] + cyc[cur.r];
		if(cur.r < ar) nxt += cyc[cur.l] + cyc[cur.r + 1];
		for(int j = nxt.l; j < cur.l; j++) dp[j] = res;
		for(int j = nxt.r; j > cur.r; j--) dp[j] = res;
		cur = nxt;
		++res;
	}
	
	int a1 = dp[al], a2 = dp[ar];
	{
		int c = al;
		while(cyc[c].r < ar){
			c = cyc[c].r; ++c; a1++;
		}
	}
	{
		int c = ar;
		while(cyc[c].l > al){
			c = cyc[c].l; ++c; a2++;
		}
	}
	ans += min(a1, a2) * 2;
	return ans;
}

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