Submission #834510

#	Time	Username	Problem	Language	Result	Execution time	Memory
834510		Josia	The Big Prize (IOI17_prize)	C++17	90 / 100	56 ms	1284 KiB

prize

#include "prize.h"
using namespace std;
#include <bits/stdc++.h>


int numBetter = 0;
set<int> candidates;

map<int, vector<int>> rem;

int getNumBetter(vector<int> x) {
	return x[0]+x[1];
}

int sol = -1;

vector<int> myAsk(int pos) {
	if (rem.count(pos)) return rem[pos];
	rem[pos] = ask(pos);
	return rem[pos];
}


void gen(int rl, int rr, int round) {
	if (rl == rr) {candidates.insert(rl); return;}
	int m = (rl + rr)/2;
	auto res = myAsk(m);
	auto left = myAsk(rl-round);
	auto right = myAsk(rr);

	if (res[0] != left[0] || getNumBetter(res)<numBetter || getNumBetter(left)<numBetter) gen(rl, m, 0);
	if (res[1] != right[1] || getNumBetter(res)<numBetter || getNumBetter(right)<numBetter) gen(m+1, rr, 1);
}


int find_best(int n) {
	candidates.clear();
	sol=-1;
	rem.clear();
	numBetter=0;

	for (int i = 0; i<min(n, 474); i++) {
		int hereBetter = getNumBetter(myAsk(i));
		if (sol != -1) return sol;
		if (hereBetter > numBetter) {
			numBetter = hereBetter;
		}
	}


	gen(0, n-1, 0);

	for (int i: candidates) {
		if (getNumBetter(myAsk(i)) == 0) return i;
	}

	assert(0);
}

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