oj.uz

Submission #1061316

# Submission time Handle Problem Language Result Execution time Memory
1061316 2024-08-16T08:00:13 Z Zicrus The Big Prize (IOI17_prize) C++17
20 / 100
 1000 ms 2132 KB 
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

typedef long long ll;

vector<pair<int, int>> cache;

pair<int, int> get(int i) {
    if (cache[i].first >= 0) return cache[i];
    auto res = ask(i);
    return cache[i] = {res[0], res[1]};
}

int find_best(int n) {
    cache = vector<pair<int, int>>(n, {-1, -1});
	int root = (int)ceil(sqrt(n));
    
    ll mxDeg = 0;
    for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
        ll deg = get(i).first + get(i).second;
        if (deg == 0) return i;
        mxDeg = max(mxDeg, deg);
    }
    int m = max(n - 2*root, 0);

    int prevLeft = 0;
    vector<bool> vst(mxDeg);
    for (int i = 0; i < mxDeg; i++) {
        if (vst[i]) continue;
        int left = prevLeft, right = m-1;
        while (left < right) {
            int mid = (left+right+1)/2;
            pair<int, int> val = get(mid);
            int deg = val.first + val.second;
            int cnt = 0;
            while (deg < mxDeg) {
                if (deg == 0) return mid;
                mid--;
                val = get(mid);
                deg = val.first + val.second;
                cnt++;
            }
            if (cnt > 0) {
                int ptr = 0;
                while (cnt--) vst[val.first + ptr++] = true;
            }
            if (vst[i]) break;
            
            if (val.first <= i) {
                left = mid;
            }
            else {
                right = mid-1;
            }
        }
        if (vst[i]) continue;

        if(get(left).first + get(left).second == 0) return left;
        vst[i] = true;
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1880 KB Output is correct
2 Correct 6 ms 1960 KB Output is correct
3 Correct 7 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 5 ms 1960 KB Output is correct
6 Correct 5 ms 1880 KB Output is correct
7 Correct 7 ms 1968 KB Output is correct
8 Correct 6 ms 1880 KB Output is correct
9 Correct 7 ms 1880 KB Output is correct
10 Correct 9 ms 1880 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1880 KB Output is correct
2 Correct 6 ms 1964 KB Output is correct
3 Correct 7 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 5 ms 1880 KB Output is correct
6 Correct 5 ms 1880 KB Output is correct
7 Correct 6 ms 1964 KB Output is correct
8 Correct 5 ms 1964 KB Output is correct
9 Correct 6 ms 1880 KB Output is correct
10 Correct 7 ms 1880 KB Output is correct
11 Correct 7 ms 1960 KB Output is correct
12 Correct 7 ms 1968 KB Output is correct
13 Correct 7 ms 1968 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 9 ms 1880 KB Output is correct
16 Correct 24 ms 2132 KB Output is correct
17 Correct 5 ms 1880 KB Output is correct
18 Correct 3 ms 1968 KB Output is correct
19 Correct 6 ms 1964 KB Output is correct
20 Correct 8 ms 1112 KB Output is correct
21 Correct 14 ms 1880 KB Output is correct
22 Correct 6 ms 1880 KB Output is correct
23 Correct 4 ms 1876 KB Output is correct
24 Correct 5 ms 1956 KB Output is correct
25 Execution timed out 3043 ms 1940 KB Time limit exceeded
26 Halted 0 ms 0 KB -