Submission #1067549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1067549	2024-08-20T20:04:17 Z	Ignut	The Big Prize (IOI17_prize)	C++17	20 / 100	58 ms	1256 KB

prize

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> ask(int i);

map<int, vector<int>> mp;

int Q = 0;

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

int SZ = 500;

int n;

int L = -1;
vector<int> GetVec(int pos) {
	vector<int> res;
	for (int i = pos; i >= max(L + 1, 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]);
	}
	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;
			bool goRight = false;
			for (int v : GetVec(mid)) {
				vector<int> vec = Ask(v);
				if (vec[0] + vec[1] == 0)
					return v;
				if (vec[0] == 0) goRight = true;
				if (vec[0] + vec[1] != cntB) continue;
				val = v;
				break;
			}
			vector<int> vec = Ask(val);
			if (vec[0] > i && !goRight)
				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	3 ms	344 KB	Output is correct
2	Correct	3 ms	344 KB	Output is correct
3	Correct	3 ms	428 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	4 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	3 ms	424 KB	Output is correct
8	Correct	4 ms	344 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	2 ms	344 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Correct	3 ms	600 KB	Output is correct
3	Correct	3 ms	344 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	4 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	3 ms	344 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	3 ms	344 KB	Output is correct
11	Correct	4 ms	344 KB	Output is correct
12	Correct	3 ms	344 KB	Output is correct
13	Correct	8 ms	344 KB	Output is correct
14	Correct	5 ms	600 KB	Output is correct
15	Correct	10 ms	856 KB	Output is correct
16	Partially correct	54 ms	1036 KB	Partially correct - number of queries: 6889
17	Correct	2 ms	344 KB	Output is correct
18	Partially correct	58 ms	1256 KB	Partially correct - number of queries: 8002
19	Correct	2 ms	344 KB	Output is correct
20	Correct	15 ms	664 KB	Output is correct
21	Incorrect	33 ms	848 KB	answer is not correct
22	Halted	0 ms	0 KB	-