Submission #113572

#	Time	Username	Problem	Language	Result	Execution time	Memory
113572		E869120	Ancient Books (IOI17_books)	C++14	50 / 100	171 ms	16156 KiB

books

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

int n, cnt[1000009];

long long solve_subtask3(vector<int>p, int s) {
	n = p.size(); int maxn = 0;
	for (int i = 0; i < n; i++) {
		int u = i, v = p[i]; if (u > v) swap(u, v); if (u != v) { maxn = max(maxn, max(u, v)); }
		cnt[u]++; cnt[v]--;
	}
	for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
	
	long long sum = 0; for (int i = 0; i < n; i++) sum += 1LL * abs(p[i] - i);
	for (int i = 0; i < maxn; i++) { if (cnt[i] == 0) sum += 2; }
	return sum;
}

vector<int> G[1009]; int cnts;
bool used[1009]; int cl[1009], cr[1009], pre[1009][1009], dp[1009][1009];
pair<int, int> nex[1009][1009];

long long solve_subtask4(vector<int> p, int s) {
	n = p.size(); int gl = s, gr = s;
	for (int i = 0; i < n; i++) {
		if (p[i] != i) { gl = min(gl, i); gr = max(gr, i); }
		if (used[i] == true || p[i] == i) continue;
		
		int cx = i; cl[cnts] = n - 1; cr[cnts] = 0;
		while (used[cx] == false) {
			used[cx] = true;
			G[cnts].push_back(cx);
			cl[cnts] = min(cl[cnts], cx);
			cr[cnts] = max(cr[cnts], cx);
			cx = p[cx];
		}
		cnts++;
	}
	
	if (gl > gr) return 0;
	
	// ------------------------ DP の前処理 --------------------------
	for (int i = 0; i < cnts; i++) { for (int j = 0; j <= n; j++) pre[i][j] = n; }
	for (int i = 0; i < cnts; i++) {
		for (int j : G[i]) pre[i][j] = j;
	}
	for (int i = 0; i < cnts; i++) {
		for (int j = n - 1; j >= 0; j--) pre[i][j] = min(pre[i][j], pre[i][j + 1]);
	}
	
	for (int pl = 0; pl < n; pl++) {
		for (int pr = pl; pr < n; pr++) {
			nex[pl][pr] = make_pair(pl, pr);
			
			for (int k = 0; k < cnts; k++) {
				if (pl <= cl[k] && cr[k] <= pr) continue;
				if (pre[k][pl] > pr) continue;
				
				nex[pl][pr] = make_pair(min(cl[k], pl), max(cr[k], pr));
				break;
			}
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < n - i; j++) {
			int pl = j, pr = j + i;
			nex[pl][pr] = nex[nex[pl][pr].first][nex[pl][pr].second];
		}
	}
	
	// ---------------------- DP の遷移 ---------------------
	for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) dp[i][j] = (1 << 30); }
	dp[nex[s][s].first][nex[s][s].second] = 0;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			int pl = j, pr = j + i;
			if (dp[pl][pr] == (1 << 30)) continue;
			
			pair<int, int> minx = make_pair((1 << 25), 0);
			for (int k = 0; k < cnts; k++) {
				if (cl[k] == cr[k]) continue;
				if (pl <= cl[k] && cr[k] <= pr) continue;
				
				int pos1 = lower_bound(G[k].begin(), G[k].end(), pl) - G[k].begin(); pos1--;
				int pos2 = lower_bound(G[k].begin(), G[k].end(), pr + 1) - G[k].begin();
				
				int rem = (1 << 30);
				if (pos1 >= 0) rem = min(rem, pl - G[k][pos1]);
				if (pos2 < G[k].size()) rem = min(rem, G[k][pos2] - pr);
				
				minx = min(minx, make_pair(rem, k));
			}
			
			int el = min(pl, cl[minx.second]), er = max(pr, cr[minx.second]);
			int fl = nex[el][er].first, fr = nex[el][er].second;
			dp[fl][fr] = min(dp[fl][fr], dp[pl][pr] + 2 * minx.first);
		}
	}
	
	long long addition = 0;
	for (int i = 0; i < n; i++) addition += abs(p[i] - i);
	return dp[gl][gr] + addition;
}

long long minimum_walk(vector<int> p, int s) {
	if (p.size() <= 1000) return solve_subtask4(p, s);
	return solve_subtask3(p, s);
}

Compilation message (stderr)

books.cpp: In function 'long long int solve_subtask4(std::vector<int>, int)':
books.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos2 < G[k].size()) rem = min(rem, G[k][pos2] - pr);
         ~~~~~^~~~~~~~~~~~~

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