oj.uz

Submission #135646

# Submission time Handle Problem Language Result Execution time Memory
135646 2019-07-24T09:18:43 Z win11905 The Big Prize (IOI17_prize) C++11
0 / 100
 101 ms 308 KB 
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

int con = 450;

int find_best(int n) {
	if(n <= 10000) {
		for(int i = 0; i < 10000; ++i) {
			vector<int> ret = ask(i);
			if(ret[0] + ret[1] == 0) return i;
		}
	}
	int mx = 0;
	for(int i = 0; i < con; ++i) {
		vector<int> ret = ask(i);
		mx = max(mx, ret[0] + ret[1]);
		if(ret[0] + ret[1] == 0) return i;
	}
	int ptr = con;
	while(ptr < n) {
		vector<int> ret = ask(ptr);
		if(ret[0] + ret[1] == 0) return ptr;
		if(ret[0] + ret[1] == mx) {
			int l = ptr, r = n-1;
			while(l < r) {
				int m = (l + r) >> 1;
				if(ret == ask(m)) l = m;
				else r = m-1;
			}
			ptr = l;
		}
		ptr++;
	}
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 248 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 308 KB Incorrect
2 Halted 0 ms 0 KB -