Submission #73365

#	Time	Username	Problem	Language	Result	Execution time	Memory
73365		SmsS	The Big Prize (IOI17_prize)	C++17	20 / 100	108 ms	692 KiB

prize

#include<bits/stdc++.h>
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "prize.h"

const bool test = 0;

int mn;
int cnt = 0;

int solve(int l,int r,vector<int> L,vector<int> R){
	if(cnt >= 9200){
		assert(0);
	}
	if(l >= r) return -1;
	if(L[1]-R[1] == 0) return -1;
//	cout << l << ' ' << r << endl;
	int mid = (l+r)/2;
	vector<int> MIDL,MIDR;
	int midl;
	int midr;
	midl = midr = mid;
	midr++;
	while(1){
		MIDL = ask(midl);
		cnt++;
		if(MIDL[0]+MIDL[1] == 0) return midl;
		if(MIDL[0]+MIDL[1] != mn){
			midl--;
		}else break;
	}
	while(1){
		MIDR = ask(midr);
		cnt++;
		if(MIDR[0]+MIDR[1] == 0) return midr;
		if(MIDR[0]+MIDR[1] != mn){
			midr++;
		}else break;
	}
	int res;
	res = solve(l,midl,L,MIDL);

	if(res == -1) return solve(midr,r,MIDR,R);
	else return res;
}

int find_best(int n) {

	if(!test && n <= 5000){
		for2(i,0,n){
			vector<int> res = ask(i);
			if(res[0]+res[1] == 0) return i;
		}
	}
	srand(14);
	for2(rep,0,10){
		vector<int> res = ask(rand()%n);
		mn = max(mn,res[0]+res[1]);
	}
	int l,r;
	vector<int> L,R;
	for2(i,0,n){
		l = i;
		L = ask(i);
		cnt++;
		if(L[0]+L[1] == mn){
			break;
		}
		if(L[0]+L[1] == 0) return i;
	}
	for(int i = n-1; i >= 0; i--){
		r = i;
		R = ask(i);
		cnt++;
		if(R[0]+R[1] == mn){
			break;
		}
		if(R[0]+R[1] == 0) return i;
	}
	return solve(l,r,L,R);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:80:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return solve(l,r,L,R);
                      ^
prize.cpp:80:22: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]

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