Submission #289171

#	Time	Username	Problem	Language	Result	Execution time	Memory
289171		Touubs	The Big Prize (IOI17_prize)	C++17	95.16 / 100	76 ms	5408 KiB

prize

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

int non_worst_box_cnt = 0;


bool notworst(vector<int> res) {
    return (res[0] + res[1] != non_worst_box_cnt);
}

bool best(vector<int> res) {
    return (res[0] + res[1] == 0);
}

bool contains(int a, vector<int> ares, int b, vector<int> bres) {
    //cout << " checking between " << a << " and " << b << "\n";
    return bres[0] != ares[0];
}

vector<vector<int>> askcache(200000);
vector<bool> asked(200000);

vector<int> ask_(int i) {
    //cout << "asking " << i << "\n";
    if (!asked[i]) {
	asked[i] = true;
	askcache[i] = ask(i);
    }
    return askcache[i];
}

int binary_search(int min, int max) {
    if (min > max) return -1;
    if (min == max) {
	if (best(ask_(min))) return min;
	return -1;
    }
    int mid = (min + max) / 2;
    auto minres = ask_(min);
    if (notworst(minres)) {
	if (best(minres)) {
	    return min;
	}
	return binary_search(min + 1, max);
    }
    auto maxres = ask_(max);
    if (notworst(maxres)) {
	if (best(maxres)) {
	    return max;
	}
	return binary_search(min, max - 1);
    }
    auto midres = ask_(mid);
    if (notworst(midres)) {
	if (best(midres)) {
	    return mid;
	}
	if (min + 2 < max)
	return std::max(binary_search(min, mid), binary_search(mid, max));
	else
	return std::max(binary_search(min, mid), binary_search(mid + 1, max));

    }
    int opt = -1;
    if (contains(min, minres, mid, midres)) {
	opt = std::max(opt, binary_search(min, mid));
    }
    if (contains(mid, midres, max, maxres)) {
	if (min + 2 < max)
	opt = std::max(opt, binary_search(mid, max));
	else 
	opt = std::max(opt, binary_search(mid + 1, max));
    }
    return opt;
}

int find_best(int n) {

    for (int i = 0; i < 475 && i < n; i++) {
	auto v = ask_(i);
	int va = v[0];
	int vb = v[1];
	non_worst_box_cnt = max(non_worst_box_cnt, va + vb);
    }

    return binary_search(0, n - 1);

}

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