Submission #650015

#	Time	Username	Problem	Language	Result	Execution time	Memory
650015		Clan328	The Big Prize (IOI17_prize)	C++17	20 / 100	43 ms	9024 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
	vector<int> t;

	SegmentTree(int n) {
		t = vector<int>(4*n);
	}

	int get(int v, int tl, int tr, int l, int r) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return t[v];
		else {
			int tm = (tl+tr)/2;
			return get(2*v, tl, tm, l, min(r, tm))+get(2*v+1, tm+1, tr, max(l, tm+1), r);
		}
	}

	void update(int v, int tl, int tr, int pos) {
		if (tl == tr) t[v]++;
		else {
			int tm = (tl+tr)/2;
			if (pos <= tm) update(2*v, tl, tm, pos);
			else update(2*v+1, tm+1, tr, pos);
			t[v] = t[2*v]+t[2*v+1];
		}
	}
};

map<int, vector<int>> dp;

vector<int> askDP(int i) {
	if (dp.count(i)) return dp[i];
	dp[i] = ask(i);
	return dp[i];
}

int find_best(int n) {
	dp = map<int, vector<int>>();

	// While not all are found
	int mxNum = 0;
	for (int i = 0; i < min(473, n); i++) {
		vector<int> ans = askDP(i);
		mxNum = max(ans[0]+ans[1]+1, mxNum);
	}

	SegmentTree tree(n);

	vector<int> arr(n);
	iota(arr.begin(), arr.end(), 0);
	int d = -1;
	while (d == -1) {
		int lo = 0, hi = arr.size(), idx = -1, mid;
		while (lo <= hi) {
			mid = (lo+hi)/2;
			vector<int> ans = askDP(arr[mid]);
			if (ans[0] == 0 && ans[1] == 0) {
				d = arr[mid];
				idx = mid;
				break;
			} else if (ans[0]+ans[1]+1 != mxNum) {
				idx = mid;
				break;
			} else if (ans[0] > tree.get(1, 0, n-1, 0, arr[mid]-1)) {
				hi = mid - 1;
			} else
				lo = mid + 1;
		}

		assert(idx != -1);

		tree.update(1, 0, n-1, arr[idx]);
		// arr.erase(arr.begin()+idx);
	}

	return d;
}

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