Submission #834485

#	Time	Username	Problem	Language	Result	Execution time	Memory
834485		Josia	The Big Prize (IOI17_prize)	C++17	99.52 / 100	47 ms	1060 KiB

prize

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


int numBetter = 0;


map<int, vector<int>> rem;

set<pair<int, int>> BSstuff;

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);

	if (getNumBetter(rem[pos]) == numBetter) {
		BSstuff.insert({-rem[pos][1], pos});
	}

	if (getNumBetter(rem[pos]) == 0) sol = pos;

	return rem[pos];
}





int find_best(int n) {
	sol=-1;
	rem.clear();
	numBetter=0;
	BSstuff.clear();
	BSstuff.insert({-1e9, 0});
	BSstuff.insert({1e9, n-1});
	int ind = 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;
			ind = i;
		}
	}

	set<int> candidates;
	for (int i=0; i<ind; i++) candidates.insert(i);

	int pos = ind;
	for (int i = ind; i<min(n, 474); i++) {
		if(getNumBetter(myAsk(i))==numBetter) continue;

		candidates.insert(i);
		pos = i+1;
	}
	while(pos<n&&getNumBetter(myAsk(pos))!=numBetter) {
		candidates.insert(pos);
		pos++;
	}


	for (int j = pos; j<n; j+=250) {
		int miau = j;
		while(miau<n&&getNumBetter(myAsk(miau))!=numBetter) miau++;
	}


	while (true) {
		if ((int)candidates.size() == numBetter) break;

		int remaining = numBetter-(int)candidates.size();
		int l = max(pos+1, (*prev(BSstuff.lower_bound({-(remaining-1), -1e9}))).second);
		int r = min(n-1, (*BSstuff.lower_bound({-(remaining-1), -1e9})).second);

		while (l<r) {
			int m = (l+r)/2;
			vector<int> ans = myAsk(m);
			if (sol != -1) return sol;

			if (getNumBetter(ans) < numBetter) {
				r = m;
				continue;
			}

			if (ans[1] < numBetter-(int)candidates.size()) {
				r = m;
			}
			else l = m+1;
		}

		pos = l;

		// while (pos < n && getNumBetter(myAsk(pos)) < numBetter) {
			// if (sol != -1) return sol;
			candidates.insert(pos);
			// pos++;
		// }

		if ((int)candidates.size() == numBetter) break;

	}

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

	assert(0);
}

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