Submission #267511

#	Time	Username	Problem	Language	Result	Execution time	Memory
267511		PeppaPig	The Big Prize (IOI17_prize)	C++14	90 / 100	139 ms	11416 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > val;

vector<int> query(int i) {
	if(val[i][0] == -1) return val[i] = ask(i);
	return val[i];
}

int find_best(int n) {
	val = vector<vector<int> >(n, vector<int>(2, -1));

	int idx = -1;
	vector<int> vec(2);
	for(int i = 0; i < min(n, 480); i++) {
		vector<int> now = query(i);
		if(now[0] + now[1] == 0) return i;
		if(now[0] + now[1] > vec[0] + vec[1])
			vec = now, idx = i;
	}

	bool bad = true;
	while(1) {
		if(bad) {
			int l = idx + 1, r = n - 1;
			while(l < r) {
				int mid = (l + r) >> 1;
				vector<int> now = query(mid);
				if(make_pair(vec[0], vec[1]) != make_pair(now[0], now[1]))
					r = mid;
				else l = mid + 1;
			}
			idx = r, bad = false;
		} else {
			vector<int> now = query(idx);
			if(now[0] + now[1] == 0) return idx;
			now = query(++idx);
			if(now[0] + now[1] == vec[0] + vec[1])
				bad = true, vec = now;
		}
	}

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80