Submission #541179

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

prize

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

**/

#include <bits/stdc++.h>
#include "prize.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) {
    vector <int> resp = ask(i);
    L[i] = resp[0];
    R[i] = resp[1];
}
int getL (int i) {
    if (L[i] == -1) {
        discover(i);
    }
    return L[i];
}
int getR (int i) {
    if (R[i] == -1) {
        discover(i);
    }
    return R[i];
}
int getLR (int i) {
    return getL(i) + getR(i);
}

vector <int> findLess (const vector <int> &v) {
    assert((int) v.size() > 0);
    int cntLess = 0;
    int k = 7;
    while (k--) {
        int i = v[rand() % (int) v.size()];
        cntLess = max(cntLess, getLR(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;
            if (getLR(v[mid]) != cntLess) {
                hi = mid;
            } else if (getL(v[mid]) > (int) vless.size()) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        assert(lo < (int) v.size());
        vless.push_back(lo);
    }
    for (int &x : vless) {
        x = v[x];
    }
    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