Submission #283721

#	Time	Username	Problem	Language	Result	Execution time	Memory
283721		emanIaicepsa	커다란 상품 (IOI17_prize)	C++14	90 / 100	133 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;
	vi cur;
	while(1){
		cur = ask(l);
		if(cur[0] == 0 && cur[1] == 0) return l;
		if(cur[0] + cur[1] < mx) l++;
		else break;
	}
	while(l < n){
		int L = l, R = n-1;
		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;
		}
		assert(L != n-1);
		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:20:5: warning: control reaches end of non-void function [-Wreturn-type]
   20 |  vi cur;
      |     ^~~

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