Submission #541702

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

map <int, map <int, int>> mp;

int solve (int l, int r) {
    int mid = (l + r) / 2;
    discover(mid);
    int cntLess = L[mid] + R[mid];
    if (cntLess == 0) {
        return mid;
    }
    mp[cntLess][mid] = L[mid];
    map <int, int> :: iterator it = mp[cntLess].find(mid);
    if (l < mid && (it == mp[cntLess].begin() || L[mid] - prev(it)->second > 0)) {
        int sl = solve(l, mid - 1);
        if (sl != -1) {
            return sl;
        }
    }
    if (mid < r && (next(it) == mp[cntLess].end() || next(it)->second - L[mid] > 0)) {
        int sr = solve(mid + 1, r);
        if (sr != -1) {
            return sr;
        }
    }
    return -1;
}

int find_best (int n) {
    L = vector <int> (n, -1);
    R = vector <int> (n, -1);
    return solve(0, n - 1);
}

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