제출 #283857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283857		emanIaicepsa	The Big Prize (IOI17_prize)	C++14	90 / 100	121 ms	6136 KiB

prize

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

vi ans[200005];
int asked[200005];
vector<int> Ask(int x){
	if(!asked[x]) ans[x] = ask(x), asked[x] = 1;
	return ans[x];
}

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;
		}
		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;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:27:5: warning: control reaches end of non-void function [-Wreturn-type]
   27 |  vi cur;
      |     ^~~

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