Submission #541687

#	Time	Username	Problem	Language	Result	Execution time	Memory
541687		alextodoran	The Big Prize (IOI17_prize)	C++17	20 / 100	71 ms	3532 KiB

prize

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#pragma GCC optimize ("unroll-loops")

using namespace std;

typedef long long ll;

vector <int> ask (int i);

vector <int> L, R;

void discover (int i) {
    if (L[i] == -1) {
        vector <int> resp = ask(i);
        L[i] = resp[0];
        R[i] = resp[1];
    }
}

mt19937 rnd (time(0));

vector <int> findLess (const vector <int> &v) {
    int cntLess = 0;
    int k = 20;
    while (k--) {
        int i = v[rnd() % (int) v.size()]; discover(i);
        cntLess = max(cntLess, L[i] + R[i]);
    }
    vector <int> vless;
    while ((int) vless.size() < cntLess) {
        int lo = (vless.empty() == true ? 0 : vless.back() + 1);
        int hi = (int) v.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int i = v[mid]; discover(i);
            if (L[i] + R[i] != cntLess) {
                hi = mid;
            } else if (L[i] > (int) vless.size()) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        vless.push_back(lo);
    }
    for (int &x : vless) {
        x = v[x];
    }
    assert((int) vless.size() < (int) v.size());
    return vless;
}

int find_best (int n) {
    L = vector <int> (n, -1);
    R = vector <int> (n, -1);
    vector <int> v (n);
    iota(v.begin(), v.end(), 0);
    while ((int) v.size() > 1) {
        v = findLess(v);
    }
    return v.front();
}

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