Submission #295677

#	Time	Username	Problem	Language	Result	Execution time	Memory
295677		williamMBDK	The Big Prize (IOI17_prize)	C++14	20 / 100	3064 ms	1244 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int mxsum = 0;
map<int,vector<int>> mem;
vector<int> myask(int i){
	if(mem.count(i)) return mem[i];
	mem[i] = ask(i);
	return mem[i];
}
bool ismx(vector<int> ans){
	int s = ans[0] + ans[1];
	return s == mxsum;
}
int find_best(int N) {
	set<int> seen;
	for(int i = 0; i < min(N, 50); i++){
		vector<int> ans = myask(i);
		int s = ans[0] + ans[1];
		if(s == 0){
			return i;
		}
		seen.insert(s);
		if(s > mxsum) mxsum = s; 
	}
	int idx = 0;
	while(1){
		vector<int> ori;
		while(1){
			vector<int> ans = myask(idx);
			if(ismx(ans)) {
				ori = ans;
				break;
			}
			if(ans[0] + ans[1] == 0){
				return idx;
			}
			idx++;
		}
		int l = idx, r = N - 1;
		while(l < r){
			int m = (l + r) / 2;
			auto ans = myask(m);
			if(ans[0] + ans[1] == 0){
				return m;
			}
			if(ans[1] == ori[1]){
				l = m + 1;
			}else if(ans[1] < ori[1]){
				r = m - 1;
			}
		}
		auto t = myask(l);
		if(t[0] + t[1] == 0) return l;
		if(t[1] == ori[1]){
			idx = l + 1;
		}else{
			idx = l; 
		}
	}
	return -1;
}

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