Submission #834561

#	Time	Username	Problem	Language	Result	Execution time	Memory
834561		Josia	The Big Prize (IOI17_prize)	C++17	100 / 100	77 ms	1440 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];
}



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

	set<pair<int, vector<int>>> s;

	vector<int> queries;
	for (int i = 0; i<n; i+=max(1,n/500)) {
		int hereBetter = getNumBetter(myAsk(i));
		queries.push_back(i);
		if (sol != -1) return sol;
		if (hereBetter > numBetter) {
			numBetter = hereBetter;
		}
	}

	for (int i: queries) {
		if (getNumBetter(myAsk(i)) == numBetter) s.insert({i, myAsk(i)});
	}



	int ahhhh = 0;
	while (getNumBetter(myAsk(ahhhh)) < numBetter) {
		candidates.insert(ahhhh);
		ahhhh++;
	}
	s.insert({ahhhh, myAsk(ahhhh)});
	ahhhh = n-1;
	while (getNumBetter(myAsk(ahhhh)) < numBetter) {
		candidates.insert(ahhhh);
		ahhhh--;
	}
	s.insert({ahhhh, myAsk(ahhhh)});


	for (int i = 0; i<100; i++) {
		auto p = s.begin();

		while (next(p) != s.end()) {
			if((*p).second[0] != (*next(p)).second[0]) {
				int m = ((*p).first + (*next(p)).first)/2;

				int inc = rand()%2;
				while (getNumBetter(myAsk(m)) < numBetter) {
					candidates.insert(m);
					m+=1-2*inc;
				}
				s.insert({m, myAsk(m)});
			}
			p++;
		}
	}


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

	assert(0);
}

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