Submission #415092

#	Time	Username	Problem	Language	Result	Execution time	Memory
415092		Bill_00	The Big Prize (IOI17_prize)	C++14	90 / 100	139 ms	1864 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int l[200005],r[200005],x[200005];
int find_best(int n){
	// for(int i = 0; i < n; i++){
	// 	std::vector<int> res = ask(i);
	// 	if(res[0] + res[1] == 0)
	// 		return i;
	// }
	for(int i=0;i<n;i++){
		l[i]=r[i]=-1;
	}
	pair<int,int>k={0,-1};
	for(int i=0;i<min(473,n);i++){
		vector<int>res=ask(i);
		l[i]=res[0];
		r[i]=res[1];
		if(l[i]+r[i]==0) return i;
		k=max(k,{res[0]+res[1],i});
	}
	int beg;
	for(int i=0;i<min(473,n);i++){
		if(l[i]+r[i]==k.first){
			beg=i;
			break;
		}
	}
	for(int i=beg;i<n;i++){
		if(l[i]==-1){
			vector<int>res=ask(i);
			l[i]=res[0];
			r[i]=res[1];
		}
		// cout << l[i] << ' ' << r[i] << ' ' << i << '\n';
		if(l[i]+r[i]==0) return i;
		if(l[i]+r[i]==k.first){
			int L=i,R=n-1;
			while(L<R){
				int m=(1+L+R)>>1;
				if(l[m]==-1){
					vector<int>res=ask(m);
					l[m]=res[0];
					r[m]=res[1];
				}
				// cout << m << ' ' << l[m] << ' ' << r[m] << '\n';
				if(r[m]==r[i]){
					L=m;
				}
				else R=m-1;
			}
			i=L;
		}
		// cout << i << '\n';
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:47:17: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     if(r[m]==r[i]){
      |              ~~~^

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