Submission #778865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
778865	2023-07-10T22:25:44 Z	kingfran1907	The Big Prize (IOI17_prize)	C++14	20 / 100	71 ms	1820 KB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;
const int maxn = 2e5+10;

int l[maxn], r[maxn];
int out = -1;
int maxi = 0;

pair<int,int> query(int x) {
	if (l[x] != -1) return {l[x], r[x]};
	
	vector< int > v = ask(x);
	l[x] = v[0], r[x] = v[1];
	return {l[x], r[x]};
}

void solve(int l, int r) {
	if (l > r) return;
	if (out != -1) return;
	if (query(l).X + query(l).Y == 0) {
		out = l;
		return;
	}
	if (query(l).X + query(l).Y < maxi) {solve(l + 1, r); return;}
	if (l == r) return;
	if (query(r).X + query(r).Y == 0) {
		out = r;
		return;
	}
	if (query(r).X + query(r).Y < maxi) {solve(l, r - 1); return;}
	if (query(l).X == query(r).X) return;
	
	int mid = (l + r) / 2;
	solve(l + 1, mid);
	solve(mid + 1, r - 1);
}

int find_best(int n) {
	memset(l, -1, sizeof l);
	for (int i = 0; i < min(500, n); i++) {
		pair<int, int> tr = query(i);
		if (tr.X + tr.Y == 0) return i;
		maxi = max(maxi, tr.X + tr.Y);
	}
	solve(500, n - 1);
	assert(out != -1);
	return out;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1104 KB	Output is correct
2	Correct	2 ms	1144 KB	Output is correct
3	Correct	4 ms	1080 KB	Output is correct
4	Correct	5 ms	1068 KB	Output is correct
5	Correct	4 ms	1104 KB	Output is correct
6	Correct	1 ms	1072 KB	Output is correct
7	Correct	2 ms	1104 KB	Output is correct
8	Correct	6 ms	1080 KB	Output is correct
9	Correct	6 ms	1096 KB	Output is correct
10	Correct	6 ms	1092 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1096 KB	Output is correct
2	Correct	3 ms	1120 KB	Output is correct
3	Correct	3 ms	1104 KB	Output is correct
4	Correct	2 ms	1068 KB	Output is correct
5	Correct	3 ms	1104 KB	Output is correct
6	Correct	1 ms	976 KB	Output is correct
7	Correct	4 ms	1104 KB	Output is correct
8	Correct	2 ms	1100 KB	Output is correct
9	Correct	5 ms	1088 KB	Output is correct
10	Correct	4 ms	1096 KB	Output is correct
11	Correct	4 ms	1272 KB	Output is correct
12	Correct	5 ms	1084 KB	Output is correct
13	Correct	7 ms	1528 KB	Output is correct
14	Correct	9 ms	1088 KB	Output is correct
15	Correct	21 ms	1196 KB	Output is correct
16	Incorrect	71 ms	1820 KB	Incorrect
17	Halted	0 ms	0 KB	-