oj.uz

Submission #722577

# Submission time Handle Problem Language Result Execution time Memory
722577 2023-04-12T11:29:38 Z perohero The Big Prize (IOI17_prize) C++17
0 / 100
 7 ms 11228 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11228 KB Output is correct
2 Incorrect 5 ms 11132 KB Integer -1 violates the range [0, 199999]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Incorrect 7 ms 11220 KB Integer -1 violates the range [0, 199999]
3 Halted 0 ms 0 KB -