Submission #73390

#	Time	Username	Problem	Language	Result	Execution time	Memory
73390		SmsS	The Big Prize (IOI17_prize)	C++17	20 / 100	118 ms	648 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;
set<int> st;

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

	dn = 0;
	while(midr != r){
		MIDR = ask(midr);
		cnt++;
		if(MIDR[0]+MIDR[1] == 0) return midr;
		if(MIDR[0]+MIDR[1] != mn){
			cnt--;
			if(cnt <= 0 || !MIDR[1]){
				dn = 1;
				break;
			}
			midr++;
		}else break;
	}
	if(!dn)return solve(midr,r,MIDR,R);
	return -1;
}

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(time(NULL));
	for2(rep,0,20){
		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:92:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return solve(l,r,L,R);
                      ^
prize.cpp:92:22: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]

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