Submission #778569

#	Time	Username	Problem	Language	Result	Execution time	Memory
778569		khshg	The Big Prize (IOI17_prize)	C++14	90 / 100	89 ms	11280 KiB

prize

#include"prize.h"
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> memo;
vector<int> K(int i) {
	if(memo[i][0] != -1) return memo[i];
	return ask(i);
}

int find_best(int N) {
	memo.resize(N, {-1, -1});
	int i = 0;
	int mx = 0;
	for(; i < 473; ++i) {
		vector<int> e = K(i);
		int sum = e[0] + e[1];
		if(!sum) return i;
		mx = max(mx, e[0] + e[1]);
	}
	while(true) {
		vector<int> e = K(i);
		int sum = e[0] + e[1];
		if(!sum) return i;
		if(sum != mx) { ++i; continue; }
		int tl = i + 1, tr = N;
		while(tl < tr) {
			int tm = (tl + tr) / 2;
			vector<int> E = ask(tm);
			if(e == E) {
				tl = tm + 1;
			} else {
				tr = tm;
			}
		}
		i = tr;
	}
}

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