Submission #283717

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

prize

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

int find_best(int n) {
	if(n <= 5000){
		for(int i=0;i<n;i++){
			vi tmp = ask(i);
			if(tmp[0] + tmp[1] == 0) return i;
		}
	}
	int mx = 0;
	for(int i=0;i<5000;i+=10){
		vi tmp = ask(i);
		mx = max(mx, tmp[0] + tmp[1]);
	}

	int l = 0;
	while(1){
		vi tmp = ask(l);
		if(tmp[0] == 0 && tmp[1] == 0) return l;
		if(tmp[0] + tmp[1] < mx) l++;
		else break;
	}
	while(l < n){
		int L = l, R = n-1;
		vi cur = ask(l);
		while(L < R){
			int m = (L+R+1)/2;
			vi tmp = ask(m);
			if(tmp[0] != cur[0] || tmp[1] != cur[1]) R = m - 1;
			else L = m;
		}
		if(L == n-1) break;
		l = L+1;
		while(1){
			if(l == n) break;
			cur = ask(l);
			if(cur[0] == 0 && cur[1] == 0) return l;
			if(cur[0] + cur[1] < mx) l++;
			else break;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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