oj.uz

Submission #1063172

# Submission time Handle Problem Language Result Execution time Memory
1063172 2024-08-17T14:50:26 Z ArthuroWich The Big Prize (IOI17_prize) C++17
0 / 100
 1000 ms 11352 KB 
#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> seg(200005, {-1, -1});
int ans = -1, mx = 0;
void check(int i) {
    if (seg[i][0] == seg[i][1] && seg[i][0] == 0) {
        ans = i;
    }
}
void Ask(int i) {
    if (seg[i][0] == -1) {
        seg[i] = ask(i);
        mx = max(mx, seg[i][0]+seg[i][1]);
        check(i);
    }
}
void calc(int l, int r, int xl, int xr) {
    if (ans != -1) {
        return;
    }
    if (l == r) {
        Ask(l);
        return;
    }
    if (xl+xr >= mx) {
        return;
    }
    int m1 = (l+r)/2, m2 = (l+r)/2;
    for (; m1 > l; m1--) {
        Ask(m1);
        if (ans != -1) {
            return;
        }
        if (seg[m1][0]+seg[m1][1] == mx) {
            break;
        }
    }
    calc(l, m1, xl, seg[m1][1]);
    if (ans != -1) {
        return;
    }
    for (; m2 < r; m2++) {
        Ask(m2);
        if (ans != -1) {
            return;
        }
        if (seg[m2][0]+seg[m2][1] == mx) {
            break;
        }
    }
    calc(m2, r, seg[m2][0], xr);
}
int find_best(int n) {
    for (int i = 0; i <= min((int)sqrt(n), n-1); i++) {
        Ask(i);
    }
    calc(0, n-1, 0, 0);
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Correct 11 ms 11352 KB Output is correct
3 Correct 13 ms 11352 KB Output is correct
4 Execution timed out 3037 ms 11352 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11352 KB Output is correct
2 Correct 10 ms 11352 KB Output is correct
3 Correct 10 ms 11352 KB Output is correct
4 Execution timed out 3028 ms 11352 KB Time limit exceeded
5 Halted 0 ms 0 KB -