oj.uz

Submission #776965

# Submission time Handle Problem Language Result Execution time Memory
776965 2023-07-08T12:35:54 Z faruk The Big Prize (IOI17_prize) C++17
20 / 100
 34 ms 336 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int sqrtn = 500;

int find_best(int n) {
	sqrtn = min(sqrtn, n);
	int max_sum = 0;
	for (int i = 0; i < sqrtn; i++)
	{
		auto a = ask(i);
		max_sum = max(max_sum, a[0] + a[1]);
		if (a[0] + a[1] == 0) {
			return i;
		}
	}

	for (int i = sqrtn; i < n; i++) {
		auto val = ask(i);
		if (val[0] + val[1] != max_sum) {
			if (val[0] + val[1] == 0)
				return i;
			continue;
		}
		
		int rval = val[1];
		int l = i, r = n - 1, ans = -1;
		while (l < r) {
			int mid = (l + r) / 2;
			auto midval = ask(mid);
			if (midval[0] + midval[1] != max_sum || midval[1] < rval)
				r = mid - 1;
			else
				l = mid + 1, ans = mid;
		}

		i = ans;
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 292 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 3 ms 288 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 5 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 288 KB Output is correct
2 Correct 2 ms 288 KB Output is correct
3 Correct 5 ms 288 KB Output is correct
4 Correct 2 ms 288 KB Output is correct
5 Correct 4 ms 288 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Incorrect 34 ms 284 KB Incorrect
12 Halted 0 ms 0 KB -