Submission #650015

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
650015	2022-10-11T22:59:01 Z	Clan328	The Big Prize (IOI17_prize)	C++17	20 / 100	43 ms	9024 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4172 KB	Output is correct
2	Correct	5 ms	4256 KB	Output is correct
3	Correct	4 ms	4164 KB	Output is correct
4	Correct	8 ms	4176 KB	Output is correct
5	Correct	7 ms	4156 KB	Output is correct
6	Correct	8 ms	4248 KB	Output is correct
7	Correct	7 ms	4256 KB	Output is correct
8	Correct	6 ms	4164 KB	Output is correct
9	Correct	5 ms	4212 KB	Output is correct
10	Correct	5 ms	4188 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4256 KB	Output is correct
2	Correct	4 ms	4172 KB	Output is correct
3	Correct	6 ms	4180 KB	Output is correct
4	Correct	9 ms	4180 KB	Output is correct
5	Correct	7 ms	4168 KB	Output is correct
6	Correct	8 ms	4156 KB	Output is correct
7	Correct	4 ms	4156 KB	Output is correct
8	Correct	7 ms	4300 KB	Output is correct
9	Correct	7 ms	4256 KB	Output is correct
10	Correct	8 ms	4176 KB	Output is correct
11	Correct	9 ms	4236 KB	Output is correct
12	Correct	7 ms	4168 KB	Output is correct
13	Correct	10 ms	4300 KB	Output is correct
14	Correct	8 ms	720 KB	Output is correct
15	Correct	7 ms	4388 KB	Output is correct
16	Correct	43 ms	4632 KB	Output is correct
17	Correct	6 ms	4252 KB	Output is correct
18	Correct	35 ms	4672 KB	Output is correct
19	Correct	7 ms	4152 KB	Output is correct
20	Correct	17 ms	2308 KB	Output is correct
21	Correct	19 ms	4396 KB	Output is correct
22	Correct	10 ms	4168 KB	Output is correct
23	Correct	7 ms	4164 KB	Output is correct
24	Correct	7 ms	4256 KB	Output is correct
25	Correct	29 ms	4424 KB	Output is correct
26	Runtime error	40 ms	9024 KB	Execution killed with signal 6
27	Halted	0 ms	0 KB	-