Submission #330484

#	Time	Username	Problem	Language	Result	Execution time	Memory
330484		maximath_1	The Big Prize (IOI17_prize)	C++11	0 / 100	87 ms	368 KiB

prize

#include "prize.h"
#include <vector>
using namespace std;

int nn, lolipop;
vector<int> get;
int ans = -1;
vector<pair<int, int> > inv;

void dnc(int cl, int cr){
	if(ans != -1) return;
	if(cl > cr) return;
	int cm = (cl + cr) / 2;
	get = ask(cm);

	if(get[0] + get[1] != lolipop){
		int lf = cm - 1, rg = cm + 1;
		for(; lf >= cl; lf --){
			get = ask(lf);
			if(get[0] + get[1] == 0){
				ans = lf;
				break;
			}
			if(get[0] + get[1] == lolipop){
				lf ++;
				break;
			}
		}
		if(lf < cl) lf = cl;
		for(; rg <= cr; rg ++){
			get = ask(rg);
			if(get[0] + get[1] == 0){
				ans = rg;
				break;
			}
			if(get[0] + get[1] == lolipop){
				rg --;
				break;
			}
		}
		if(rg > cr) rg = cr;

		inv.push_back({lf, rg});
		dnc(cl, lf - 1); dnc(rg + 1, cr);
	}else{
		dnc(cl, cm - 1);
		dnc(cm + 1, cr);
	}

	return;
}

int find_best(int n){
	nn = n;

	lolipop = 0;
	int lf = 0, rg;
	for(rg = 0; rg < 474; rg ++){
		get = ask(rg);
		if(get[0] + get[1] == 0) return rg;
		if(get[0] + get[1] > lolipop)
			lolipop = get[0] + get[1];
	}

	dnc(0, n - 1);

	if(ans != -1){
		return ans;
	}

	for(auto i : inv){
		for(int j = i.first; j <= i.second; j ++){
			get = ask(j);
			if(get[0] + get[1] == 0) return j;
		}
	}

	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:57:6: warning: unused variable 'lf' [-Wunused-variable]
   57 |  int lf = 0, rg;
      |      ^~

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