Submission #868941

#	Time	Username	Problem	Language	Result	Execution time	Memory
868941		n1k	The Big Prize (IOI17_prize)	C++17	20 / 100	47 ms	600 KiB

prize

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

using namespace std;

const int LOG = 18, TAKE = 500;

int find_best(int n) {
	// find max
	int mx = 0;
	for(int i = 0; i < min(TAKE, n); i++){
		auto c = ask(i);
		int s = c[0] + c[1];
		if(s == 0) return i;
		mx = max(mx, s);
	}

	function<int(int, int)> find = [&](int l , int r){
		int cntl = 0, cntr = 0;
		for(; 1; l++){
			auto c = ask(l);
			int s = c[0] + c[1];
			if(s == 0) return l;
			cntl = c[0];
			if(s == mx){
				break;
			}
		}
		for(; 1; r--){
			auto c = ask(r);
			int s = c[0] + c[1];
			if(s == 0) return r;
			cntr = c[0];
			if(s == mx){
				break;
			}
		}
		if(cntl != cntr){
			int m = (l + r) / 2;
			int ret;
			if((ret = find(l, m)) != -1){
				return ret;
			}
			if((ret = find(m + 1, r)) != -1){
				return ret;
			}
		}
		return -1;
	};
	
	return find(0, n - 1);
}

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