oj.uz

Submission #767792

# Submission time Handle Problem Language Result Execution time Memory
767792 2023-06-27T07:33:40 Z SanguineChameleon The Big Prize (IOI17_prize) C++17
0 / 100
 12 ms 5096 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int lim = 474;
const int jump = 256;
vector<int> memo[maxn];

vector<int> get(int i) {
	if (memo[i].empty()) {
		memo[i] = ask(i);
	}
	return memo[i];
}

int find_best(int n) {
	if (n <= lim) {
		for (int i = 0; i < n; i++) {
			vector<int> res = get(i);
			if (res[0] + res[1] == 0) {
				return i;
			}
		}
	}
	int mx = 0;
	for (int i = n - lim; i < n; i++) {
		vector<int> res = get(i);
		if (res[0] + res[1] == 0) {
			return i;
		}
		mx = max(mx, res[0] + res[1]);
	}
	int cur = lim;
	while (true) {
		vector<int> res1 = get(cur);
		if (res1[0] + res1[1] == 0) {
			return cur;
		}
		if (res1[0] + res1[1] < mx) {
			cur++;
			continue;
		}
		if (cur + jump < n) {
			vector<int> res2 = get(cur + jump);
			if ((res2[0] + res2[1] == res1[0] + res1[1]) && (res2[0] == res1[0])) {
				cur += jump;
				continue;
			}
		}
		int lt = cur + 1;
		int rt = min(cur + jump - 1, n - 1);
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			vector<int> res2 = get(mt);
			if (res2[0] + res2[1] == 0) {
				return mt;
			}
			if ((res2[0] + res2[1] == res1[0] + res1[1]) && (res2[0] == res1[0])) {
				cur = mt;
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		cur++;
	}
	return -1;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5016 KB Output is correct
2 Correct 8 ms 4944 KB Output is correct
3 Correct 5 ms 5096 KB Output is correct
4 Correct 6 ms 4988 KB Output is correct
5 Correct 9 ms 5012 KB Output is correct
6 Incorrect 7 ms 5004 KB Integer 200000 violates the range [0, 199999]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4944 KB Output is correct
2 Correct 9 ms 4992 KB Output is correct
3 Correct 10 ms 4996 KB Output is correct
4 Correct 7 ms 4988 KB Output is correct
5 Correct 12 ms 4992 KB Output is correct
6 Incorrect 7 ms 5040 KB Integer 200000 violates the range [0, 199999]
7 Halted 0 ms 0 KB -