oj.uz

답안 #975447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975447 2024-05-05T08:01:10 Z pirhosig 커다란 상품 (IOI17_prize) C++17
20 / 100
 10 ms 596 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;



int find_best(int n) {
	if (n < 5000) {
		for (int i = 0; i < n; ++i) {
			auto a = ask(i);
			if (a[0] + a[1] == 0) return i;
		}
	}

	int large = 0;
	vector<int> val(450);
	for (int i = 0; i < 450; ++i) {
		auto a = ask(i);
		val[i] = a[0] + a[1];
		if (val[i] == 0) return i;
		large = max(large, val[i]);
	}

	int found = 0;
	for (int a : val) if (a != large) found++;

	int low = 450;
	for (int i = found + 1; i <= large; ++i) {
		int upp = n - 1;
		while (low < upp) {
			int mid = (low + upp) / 2;
			auto a = ask(mid);
			int tot = a[0] + a[1];
			if (tot == 0) return mid;
			if (tot < large) {
				int skip = 0;
				while (tot < large) {
					mid--;
					skip++;
					a = ask(mid);
					tot = a[0] + a[1];
					if (tot == 0) return mid;
				}
				if (a[0] + skip >= i) low = upp = mid + i - a[0];
			}

			if (a[0] < i) low = mid + 1;
			else upp = mid - 1;
		}
		auto a = ask(low);
		if (a[0] + a[1] == 0) return low;
		low++;
	}

	return -1;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 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 2 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Incorrect 10 ms 344 KB Integer -1 violates the range [0, 20999]
15 Halted 0 ms 0 KB -