Submission #1273487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273487		Lithanium	The Big Prize (IOI17_prize)	C++20	20 / 100	1076 ms	3872 KiB

prize

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

mt19937 rd(time(0));

int K = 1000; // block size
int N;

pair<int, int> cache[200005];
int nodes[800005];

void upd(int n, int l, int r, int p) {
	if (l == r) {
		nodes[n] = 1;
		return;
	}
	int mid = (l+r)/2;
	if (p <= mid) upd(2*n, l, mid, p);
	else upd(2*n+1, mid+1, r, p);
	nodes[n] = nodes[2*n] + nodes[2*n+1];
}

int query(int n, int l, int r, int ql, int qr) {
	if (l > qr or r < ql) return 0;
	if (ql <= l and r <= qr) return nodes[n];
	int mid = (l+r)/2;
	return query(2*n, l, mid, ql, qr) + query(2*n+1, mid+1, r, ql, qr);
}

pair<int, int> query(int i) {
	if (cache[i].first != -1) return cache[i];
	vector<int> v = ask(i-1);
	return cache[i] = make_pair(v[0], v[1]);
}

int sum(int i) {
	auto [x, y] = query(i);
	return x+y;
}

int find_best(int n) {
	N = n;
	for (int i = 1; i <= N; i ++) cache[i] = {-1, -1};
	// rng 50 times to find the max
	int total = 0;
	for (int t = 0; t < 50; t ++) total = max(total, sum(rd()%N+1));
	// consider each block
	for (int i = 1; i <= N; i += K) {
		// i -> min(N, i+K-1)
		int l = i, r = min(N, i+K-1);
		while (l <= r and sum(l) != total) {
			upd(1, 1, N, l);
			l ++;
		}
		while (l <= r and sum(r) != total) {
			upd(1, 1, N, r);
			r --;
		}
		if (l > r) continue;
		auto [a1, b1] = query(l);
		// keep binary searching
		while (true) {
			int low = l, high = r;
			bool found = 0;
			while (high > low) {
				int mid = (low + high)/2;
				int old = mid;
				while (query(1, 1, N, mid, mid)) mid ++;
				if (mid > high) {
					high = old-1;
					continue;
				}
				auto [x, y] = query(mid);
				if (x+y == total) {
					// subtract the special things between [l, mid]
					int sum = x - a1 - query(1, 1, N, l, mid);
					if (sum > 0) high = old-1;
					else low = mid+1;
				} else {
					upd(1, 1, N, mid);
					found = 1;
					break;
				}
			}
			if (sum(low) != total) {
				upd(1, 1, N, low);
				found = 1;
			}
			if (!found) break;
		}
	}
	for (int i = 1; i <= N; i ++) if (query(1, 1, N, i, i) and sum(i) == 0) return i-1;
	assert(0);
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80