Submission #295409

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

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int mxsum = 0;
bool ismx(vector<int> ans){
	int s = ans[0] + ans[1];
	return s == mxsum;
}
int find_best(int N) {
	for(int i = 0; i < min(N, 711); i++){
		vector<int> ans = ask(i);
		int s = ans[0] + ans[1];
		if(ans[0] + ans[1] == 0){
			return i;
		}
		if(s > mxsum) mxsum = s; 
	}
	int idx = 0;
	while(1){
		vector<int> ori;
		while(1){
			vector<int> ans = ask(idx);
			if(ismx(ans)) {
				ori = ans;
				break;
			}
			if(ans[0] + ans[1] == 0){
				return idx;
			}
			idx++;
		}
		// ori should always have length here
		// there should always be positive amount lower here
		int l = idx, r = N - 1;
		while(l <= r){
			int m = (l + r) / 2;
			auto ans = ask(m);
			if(ans[0] + ans[1] == 0){
				return m;
			}
			if(ans[1] == ori[1] && ask(m + 1)[1] != ori[1]){ // error?
				idx = m;
				break;
			}else if(ans[1] == ori[1]){
				l = m + 1;
			}else if(ans[1] < ori[1]){
				r = m - 1;
			}
		}
		idx++;
	}
	return -1;
}

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