Submission #1067544

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1067544	2024-08-20T19:58:25 Z	Ignut	The Big Prize (IOI17_prize)	C++17	20 / 100	73 ms	1616 KB

prize

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> ask(int i);

map<int, vector<int>> mp;
vector<int> Ask(int i) {
	// cout << "ask " << i << '\n';
	if (mp.count(i)) return mp[i];
	vector<int> ans = ask(i);
	mp[i] = ans;
	return ans;
}

int SZ = 1000;

int n;

vector<int> GetVec(int pos) {
	vector<int> res;
	for (int i = pos; i >= max(0, pos - SZ / 2); i --) res.push_back(pos);
	for (int i = pos + 1; i <= min(n - 1, pos + SZ / 2); i ++) res.push_back(pos);
	return res;
}

int find_best(int nn) {
	n = nn;
	int cntB = 0;
	for (int i = 0; i < min(n, SZ); i ++) {
		vector<int> vec = Ask(i);
		if (vec[0] + vec[1] == 0) return i;
		cntB = max(cntB, vec[0] + vec[1]);
	}
	int L = -1;
	for (int i = 0; i < cntB; i ++) {
		int lo = L + 1, hi = n - 1;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			int val = mid;
			for (int v : GetVec(mid)) {
				vector<int> vec = Ask(v);
				if (vec[0] + vec[1] == 0)
					return v;
				if (vec[0] + vec[1] != cntB) continue;
				val = v; break;
			}
			vector<int> vec = Ask(val);
			if (vec[0] > i)
				hi = mid - 1;
			else
				lo = mid + 1;
		}
		vector<int> vec = Ask(lo);
		if (vec[0] + vec[1] == 0) return lo;
		L = lo;
	}
	// while (L < n - 1) {
	// 	while (lo < hi) {
	// 		int mid = lo + (hi - lo) / 2;
	// 	}	
	// }
	return n - 1;
}

/*
8
3 2 3 1 3 3 2 3
*/

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	344 KB	Output is correct
2	Correct	5 ms	344 KB	Output is correct
3	Correct	5 ms	448 KB	Output is correct
4	Correct	4 ms	600 KB	Output is correct
5	Correct	3 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	4 ms	344 KB	Output is correct
8	Correct	5 ms	344 KB	Output is correct
9	Correct	5 ms	344 KB	Output is correct
10	Correct	6 ms	508 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	504 KB	Output is correct
2	Correct	5 ms	600 KB	Output is correct
3	Correct	3 ms	344 KB	Output is correct
4	Correct	4 ms	536 KB	Output is correct
5	Correct	5 ms	600 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	5 ms	600 KB	Output is correct
8	Correct	4 ms	524 KB	Output is correct
9	Correct	5 ms	344 KB	Output is correct
10	Correct	5 ms	600 KB	Output is correct
11	Correct	8 ms	344 KB	Output is correct
12	Correct	4 ms	344 KB	Output is correct
13	Correct	9 ms	600 KB	Output is correct
14	Correct	8 ms	600 KB	Output is correct
15	Correct	14 ms	592 KB	Output is correct
16	Partially correct	61 ms	1104 KB	Partially correct - number of queries: 7379
17	Correct	2 ms	344 KB	Output is correct
18	Partially correct	73 ms	1616 KB	Partially correct - number of queries: 8492
19	Correct	2 ms	344 KB	Output is correct
20	Correct	21 ms	600 KB	Output is correct
21	Incorrect	47 ms	856 KB	answer is not correct
22	Halted	0 ms	0 KB	-