oj.uz

Submission #1067542

# Submission time Handle Problem Language Result Execution time Memory
1067542 2024-08-20T19:56:02 Z Ignut The Big Prize (IOI17_prize) C++17
20 / 100
 4 ms 600 KB 
// 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 = 500;

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 = -1;
			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 3 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 3 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 2 ms 460 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Incorrect 3 ms 344 KB Integer -1 violates the range [0, 199999]
12 Halted 0 ms 0 KB -