Submission #420972

#	Time	Username	Problem	Language	Result	Execution time	Memory
420972		daanolav	The Big Prize (IOI17_prize)	C++14	20 / 100	117 ms	288 KiB

prize

#include "prize.h"
#include <tuple>
#include <queue>

using namespace std;

typedef tuple<float,int,int> fii;

int n,s,e,mid;
float amount;
std::vector<int> res;


int find_best(int n) {

    ::n = n;
	// std::vector<int> res = ask(i);
	priority_queue<fii,vector<fii>,less<fii>> q;

	res = ask(n / 2);

	if(res[0] + res[1] == 0) {
        return n / 2;
	}

	q.push({(float) res[0] / (float) (n / 2),0, n / 2 - 1});
	q.push({(float) res[1] / (float) (n - n / 2 - 1),n / 2 + 1,n - 1});

	while(!q.empty()) {
        tie(amount,s,e) = q.top();
        q.pop();

        if(s > e) {
            continue;
        }

        mid = (e + s) / 2;
        res = ask(mid);
        if(res[0] + res[1] == 0) {
            return mid;
        }

        q.push({(float) res[0] / (float) (mid - s),s,mid - 1});
        q.push({(float) res[1] / (float) (e - mid),mid + 1,e});



	}


	return 0;
}

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