Submission #73332

#	Time	Username	Problem	Language	Result	Execution time	Memory
73332		SmsS	The Big Prize (IOI17_prize)	C++17	0 / 100	132 ms	436 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 solve(int l,int r,vector<int> L,vector<int> R){
	if(l == r) return -1;
	/// if empty return -1;
	if(L[1]-R[1] == (r-l-1)) return -1;
	int mid = (l+r)/2;
	vector<int> MID = ask(mid);
	if(MID[0]+MID[1] == 0) return mid;
	int res = solve(l,mid,L,MID);
	if(res == -1) return solve(mid+1,r,MID,R);
}

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(10);
	int st = rand()%n;
	vector<int> res = ask(st);
	mn = res[0]+res[1];
	int l,r;
	vector<int> L,R;
	for2(i,0,n){
		l = i;
		L = ask(i);
		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);
		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 solve(int, int, std::vector<int>, std::vector<int>)':
prize.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:51:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return solve(l,r,L,R);
                      ^
prize.cpp:51:22: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]

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