Submission #722577

#	Time	Username	Problem	Language	Result	Execution time	Memory
722577		tvladm2009	The Big Prize (IOI17_prize)	C++17	0 / 100	7 ms	11228 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

vector <int> L, R;

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

map <int, int> mp[N_MAX + 2];

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];
    auto 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 && (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: 0 / 20
• Subtask 2: 0 / 80