oj.uz

Submission #1061306

# Submission time Handle Problem Language Result Execution time Memory
1061306 2024-08-16T07:57:07 Z Zicrus The Big Prize (IOI17_prize) C++17
20 / 100
 965 ms 1048576 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;
    vector<vector<ll>> degBoxes(n);
    set<ll> degs;
    for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
        ll deg = get(i).first + get(i).second;
        degBoxes[deg].push_back(i);
        mxDeg = max(mxDeg, deg);
        degs.insert(deg);
    }
    int m = max(n - 2*root, 0);
    if (!degBoxes[0].empty()) {
        return degBoxes[0][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) {
                degBoxes[deg].push_back(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;

        degBoxes[get(left).first + get(left).second].push_back(left);
        vst[i] = true;
    }

    return degBoxes[0][0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 7 ms 6488 KB Output is correct
4 Correct 8 ms 6488 KB Output is correct
5 Correct 8 ms 6488 KB Output is correct
6 Correct 6 ms 6488 KB Output is correct
7 Correct 6 ms 6488 KB Output is correct
8 Correct 7 ms 6488 KB Output is correct
9 Correct 5 ms 6488 KB Output is correct
10 Correct 7 ms 6744 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6488 KB Output is correct
2 Correct 5 ms 6488 KB Output is correct
3 Correct 6 ms 6728 KB Output is correct
4 Correct 6 ms 6488 KB Output is correct
5 Correct 6 ms 6488 KB Output is correct
6 Correct 8 ms 6488 KB Output is correct
7 Correct 6 ms 6488 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 4 ms 6488 KB Output is correct
10 Correct 6 ms 6488 KB Output is correct
11 Correct 8 ms 6488 KB Output is correct
12 Correct 10 ms 6488 KB Output is correct
13 Correct 7 ms 6488 KB Output is correct
14 Correct 6 ms 1120 KB Output is correct
15 Correct 32 ms 6720 KB Output is correct
16 Partially correct 27 ms 6708 KB Partially correct - number of queries: 5183
17 Partially correct 21 ms 6968 KB Partially correct - number of queries: 5191
18 Correct 6 ms 6720 KB Output is correct
19 Correct 32 ms 6728 KB Output is correct
20 Runtime error 965 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -