oj.uz

Submission #1080994

# Submission time Handle Problem Language Result Execution time Memory
1080994 2024-08-29T16:42:43 Z qwusha The Big Prize (IOI17_prize) C++17
0 / 100
 3 ms 416 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#include <prize.h>

int find_best(int n) {
    vector<pair<int, int>> s;
    for (int i = 0; i < min(n, 500); i++) {
        vector<int> res = ask(i);
        s.push_back({res[0] + res[1], -i});
    }
    sort(s.rbegin(), s.rend());
    int ind = -(s[0].se);
    int cur = s[0].fi;
    int val = s[0].fi;
    while(true) {
        int l = ind, r = n;
        int last = -1;
        while (r - l > 1) {
            int m = (r + l) / 2;
            auto an = ask(m);
            if (cur == an[1]) {
                l = m;
            } else {
                r = m;
                last = an[1];
            }
        }
        if (last == 0) {
            return r;
        }
        ind = r;
        vector<int> an = ask(ind);
        while (an[0] + an[1] < val) {
            if (an[1] == 0) {
                return ind;
            }
            ind++;
            an = ask(ind);
        }
        last = an[1];
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 3 ms 344 KB answer is not correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 3 ms 344 KB answer is not correct
7 Halted 0 ms 0 KB -