Submission #113567

#	Time	Username	Problem	Language	Result	Execution time	Memory
113567		E869120	Ancient Books (IOI17_books)	C++14	50 / 100	168 ms	39872 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[1000009]; int cnts;
bool used[1000009]; int cl[1000009], cr[1000009];

long long solve_subtask4(vector<int> p, int s) {
	n = p.size();
	for (int i = 0; i < n; i++) {
		if (used[i] == true) 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++;
	}
	
	for (int i = 0; i < cnts; i++) sort(G[i].begin(), G[i].end());
	
	int pl = s, pr = s; long long totalcost = 0;
	while (true) {
		bool flag = false; int ret = 0;
		for (int i = 0; i < cnts; i++) {
			if (cl[i] == cr[i]) continue;
			if (pl <= cl[i] && cr[i] <= pr) continue;
			
			ret++;
			int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin();
			int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
			if (pos2 - pos1 >= 1) { pl = min(pl, cl[i]); pr = max(pr, cr[i]); flag = true; }
		}
		if (ret == 0) break;
		if (flag == true) continue;
		
		pair<long long, int> minx = make_pair((1 << 30), 0);
		for (int i = 0; i < cnts; i++) {
			if (cl[i] == cr[i]) continue;
			if (pl <= cl[i] && cr[i] <= pr) continue;
			
			int pos1 = lower_bound(G[i].begin(), G[i].end(), pl) - G[i].begin(); pos1--;
			int pos2 = lower_bound(G[i].begin(), G[i].end(), pr + 1) - G[i].begin();
			
			long long rem = (1 << 30);
			if (pos1 >= 0) rem = min(rem, 1LL * pl - 1LL * G[i][pos1]);
			if (pos2 < G[i].size()) rem = min(rem, 1LL * G[i][pos2] - 1LL * pr);
			
			minx = min(minx, make_pair(rem, i));
		}
		
		totalcost += 2LL * minx.first;
		pl = min(pl, cl[minx.second]);
		pr = max(pr, cr[minx.second]);
	}
	for (int i = 0; i < n; i++) totalcost += 1LL * abs(p[i] - i);
	return totalcost;
}

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:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pos2 < G[i].size()) rem = min(rem, 1LL * G[i][pos2] - 1LL * pr);
        ~~~~~^~~~~~~~~~~~~

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