oj.uz

Submission #1065436

# Submission time Handle Problem Language Result Execution time Memory
1065436 2024-08-19T07:35:19 Z mc061 The Big Prize (IOI17_prize) C++17
90 / 100
 70 ms 2600 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+6;
bool is_worst[N]={};
bool know[N]={};
pair<int, int> val[N];

int C = 0;

unordered_map<int, set<int, greater<int>>> last_by_sum;

vector<int> ask(int i);

pair<int, int> get(int i) {
    if (know[i]) {
        return val[i];
    }
    ++C;
    assert(C <= 10000);
    know[i] = true;
    auto now = ask(i);
    val[i].first = now[0], val[i].second = now[1];
    last_by_sum[now[0] + now[1]].insert(i);
    return {now[0], now[1]};
}

int find_best(int n) {
    int mx = 0;
    for (int i = 0; i < min(n, 550); ++i) {
        auto now = get(i);
        val[i].first = now.first;
        val[i].second = now.second;
        mx = max(mx, val[i].first + val[i].second);
        last_by_sum[val[i].first + val[i].second].insert(i);
        if (val[i].first + val[i].second == 0) return i; 
    }
    for (int i = 0; i < min(n, 550); ++i) {
        if (val[i].first + val[i].second == mx) {
            is_worst[i] = true;
            know[i] = true;
        }
        if (val[i].first + val[i].second == 0) return i;
    }
    int l = 550;
    while (true) {
        auto now = get(l);
        if (now.first + now.second == 0) return l;
        
        if (now.first + now.second == mx) break;
        ++l;
    }
    while (true) {
        int low = l+1, high = n-1;
        int pl = l;
        while (high != low) {
            int mid = (high + low + 1) >> 1;
            auto now = get(mid);
            int sum = now.first + now.second;
            if (sum == mx) {
                if (now.first == val[l].first) {
                    low = mid+1;
                }
                else {
                    high = mid-1;
                }
                continue;
            }
            if (now.first + now.second == 0) return mid;
            int v = mid;
            bool worth_left = true;
            while (sum < mx && worth_left) {
                --v;
                now = get(v);
                sum = now.first + now.second;
                if (sum == mx) break;
                if (val[v].second > 0) {
                    worth_left = false;
                    break;
                }
                set<int, greater<int>>& s = last_by_sum[sum];
                auto it = s.upper_bound(v);
                if (it != s.end()) {
                    if (val[v].first == val[*it].first || val[v].second > 0) {
                        worth_left = false;
                        break;
                    }
                }
                if (sum == 0) return v;
            }
            if (!worth_left) {
                int v = mid;
                get(v);
                sum = val[v].first + val[v].second;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            if (now.first == val[l].first) {
                int v = mid;
                sum = val[v].first + val[v].second;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            high = v-1;
        }
        if (pl == l) {
            auto x = get(low);
            if (x.first + x.second == 0) return low;
            l = low+1;
            get(l);
            int sum = val[l].first + val[l].second;
            if (sum == 0) return l;
            while (sum < mx) {
                ++l;
                get(l);
                sum = val[l].first + val[l].second;
                if (sum == 0) return l;
            }
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 452 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 5 ms 1108 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 6 ms 1232 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 8 ms 1192 KB Output is correct
16 Partially correct 45 ms 2264 KB Partially correct - number of queries: 7019
17 Correct 2 ms 344 KB Output is correct
18 Partially correct 33 ms 2356 KB Partially correct - number of queries: 8135
19 Correct 2 ms 344 KB Output is correct
20 Correct 8 ms 1112 KB Output is correct
21 Correct 17 ms 1616 KB Output is correct
22 Correct 8 ms 1112 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 38 ms 2056 KB Output is correct
26 Correct 17 ms 1872 KB Output is correct
27 Correct 3 ms 600 KB Output is correct
28 Partially correct 42 ms 2468 KB Partially correct - number of queries: 7672
29 Partially correct 41 ms 2296 KB Partially correct - number of queries: 5986
30 Partially correct 49 ms 2384 KB Partially correct - number of queries: 8115
31 Correct 3 ms 344 KB Output is correct
32 Correct 5 ms 1208 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 14 ms 1624 KB Output is correct
35 Correct 4 ms 856 KB Output is correct
36 Correct 13 ms 1368 KB Output is correct
37 Correct 6 ms 600 KB Output is correct
38 Correct 3 ms 456 KB Output is correct
39 Correct 23 ms 1872 KB Output is correct
40 Partially correct 38 ms 2324 KB Partially correct - number of queries: 7025
41 Partially correct 33 ms 2120 KB Partially correct - number of queries: 5109
42 Partially correct 37 ms 2128 KB Partially correct - number of queries: 5109
43 Correct 19 ms 1880 KB Output is correct
44 Correct 17 ms 1768 KB Output is correct
45 Correct 16 ms 1616 KB Output is correct
46 Correct 3 ms 448 KB Output is correct
47 Correct 19 ms 1872 KB Output is correct
48 Partially correct 35 ms 2128 KB Partially correct - number of queries: 6210
49 Correct 5 ms 856 KB Output is correct
50 Partially correct 48 ms 2508 KB Partially correct - number of queries: 8110
51 Correct 25 ms 2108 KB Output is correct
52 Correct 3 ms 344 KB Output is correct
53 Correct 5 ms 600 KB Output is correct
54 Correct 20 ms 1804 KB Output is correct
55 Correct 2 ms 472 KB Output is correct
56 Partially correct 70 ms 2388 KB Partially correct - number of queries: 8159
57 Partially correct 42 ms 2592 KB Partially correct - number of queries: 6100
58 Partially correct 35 ms 2208 KB Partially correct - number of queries: 6146
59 Partially correct 27 ms 2036 KB Partially correct - number of queries: 5109
60 Correct 34 ms 1936 KB Output is correct
61 Correct 4 ms 728 KB Output is correct
62 Correct 4 ms 344 KB Output is correct
63 Correct 5 ms 712 KB Output is correct
64 Correct 5 ms 344 KB Output is correct
65 Correct 4 ms 856 KB Output is correct
66 Correct 5 ms 340 KB Output is correct
67 Correct 3 ms 344 KB Output is correct
68 Correct 3 ms 344 KB Output is correct
69 Correct 7 ms 344 KB Output is correct
70 Correct 5 ms 860 KB Output is correct
71 Partially correct 61 ms 2384 KB Partially correct - number of queries: 8357
72 Correct 6 ms 1504 KB Output is correct
73 Partially correct 46 ms 2384 KB Partially correct - number of queries: 8234
74 Partially correct 53 ms 2356 KB Partially correct - number of queries: 8281
75 Correct 4 ms 856 KB Output is correct
76 Partially correct 33 ms 2380 KB Partially correct - number of queries: 7170
77 Partially correct 51 ms 2600 KB Partially correct - number of queries: 8192
78 Correct 7 ms 1500 KB Output is correct
79 Correct 18 ms 2284 KB Output is correct
80 Partially correct 50 ms 2388 KB Partially correct - number of queries: 8230
81 Partially correct 44 ms 2516 KB Partially correct - number of queries: 8203
82 Partially correct 51 ms 2492 KB Partially correct - number of queries: 8111
83 Correct 4 ms 856 KB Output is correct
84 Partially correct 30 ms 2384 KB Partially correct - number of queries: 6786
85 Partially correct 47 ms 2544 KB Partially correct - number of queries: 8172
86 Correct 4 ms 344 KB Output is correct
87 Correct 3 ms 344 KB Output is correct
88 Correct 4 ms 344 KB Output is correct
89 Correct 3 ms 344 KB Output is correct
90 Correct 2 ms 344 KB Output is correct
91 Correct 2 ms 600 KB Output is correct
92 Correct 3 ms 344 KB Output is correct
93 Correct 5 ms 1368 KB Output is correct
94 Correct 5 ms 1312 KB Output is correct
95 Correct 5 ms 1112 KB Output is correct
96 Correct 4 ms 1112 KB Output is correct
97 Correct 3 ms 344 KB Output is correct