oj.uz

Submission #1065431

# Submission time Handle Problem Language Result Execution time Memory
1065431 2024-08-19T07:33:05 Z mc061 The Big Prize (IOI17_prize) C++17
90 / 100
 57 ms 2760 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;
                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) {
                        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 3 ms 344 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 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 5 ms 472 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 444 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 8 ms 1468 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 8 ms 1168 KB Output is correct
16 Partially correct 36 ms 2312 KB Partially correct - number of queries: 7019
17 Correct 2 ms 344 KB Output is correct
18 Partially correct 42 ms 2712 KB Partially correct - number of queries: 8135
19 Correct 2 ms 440 KB Output is correct
20 Correct 18 ms 1112 KB Output is correct
21 Correct 21 ms 1644 KB Output is correct
22 Correct 5 ms 856 KB Output is correct
23 Correct 4 ms 344 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 20 ms 1900 KB Output is correct
26 Correct 34 ms 1880 KB Output is correct
27 Correct 5 ms 600 KB Output is correct
28 Partially correct 54 ms 2388 KB Partially correct - number of queries: 7672
29 Partially correct 40 ms 2408 KB Partially correct - number of queries: 5986
30 Partially correct 35 ms 2376 KB Partially correct - number of queries: 8115
31 Correct 2 ms 344 KB Output is correct
32 Correct 4 ms 1112 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 14 ms 1528 KB Output is correct
35 Correct 4 ms 856 KB Output is correct
36 Correct 17 ms 1460 KB Output is correct
37 Correct 4 ms 600 KB Output is correct
38 Correct 3 ms 600 KB Output is correct
39 Correct 21 ms 1988 KB Output is correct
40 Partially correct 35 ms 2392 KB Partially correct - number of queries: 7025
41 Partially correct 25 ms 1872 KB Partially correct - number of queries: 5109
42 Partially correct 31 ms 1952 KB Partially correct - number of queries: 5109
43 Correct 16 ms 1872 KB Output is correct
44 Correct 22 ms 1760 KB Output is correct
45 Correct 14 ms 1624 KB Output is correct
46 Correct 3 ms 344 KB Output is correct
47 Correct 33 ms 1892 KB Output is correct
48 Partially correct 27 ms 2132 KB Partially correct - number of queries: 6210
49 Correct 5 ms 856 KB Output is correct
50 Partially correct 54 ms 2700 KB Partially correct - number of queries: 8110
51 Correct 18 ms 1616 KB Output is correct
52 Correct 3 ms 344 KB Output is correct
53 Correct 4 ms 692 KB Output is correct
54 Correct 16 ms 1732 KB Output is correct
55 Correct 2 ms 344 KB Output is correct
56 Partially correct 37 ms 2656 KB Partially correct - number of queries: 8159
57 Partially correct 31 ms 2132 KB Partially correct - number of queries: 6100
58 Partially correct 23 ms 2128 KB Partially correct - number of queries: 6146
59 Partially correct 34 ms 1920 KB Partially correct - number of queries: 5109
60 Correct 23 ms 1872 KB Output is correct
61 Correct 5 ms 856 KB Output is correct
62 Correct 2 ms 344 KB Output is correct
63 Correct 4 ms 600 KB Output is correct
64 Correct 4 ms 344 KB Output is correct
65 Correct 4 ms 344 KB Output is correct
66 Correct 8 ms 344 KB Output is correct
67 Correct 4 ms 344 KB Output is correct
68 Correct 3 ms 344 KB Output is correct
69 Correct 5 ms 344 KB Output is correct
70 Correct 3 ms 344 KB Output is correct
71 Partially correct 47 ms 2344 KB Partially correct - number of queries: 8357
72 Correct 6 ms 1368 KB Output is correct
73 Partially correct 57 ms 2464 KB Partially correct - number of queries: 8234
74 Partially correct 37 ms 2328 KB Partially correct - number of queries: 8281
75 Correct 5 ms 856 KB Output is correct
76 Partially correct 44 ms 2608 KB Partially correct - number of queries: 7170
77 Partially correct 37 ms 2416 KB Partially correct - number of queries: 8192
78 Correct 5 ms 1368 KB Output is correct
79 Correct 25 ms 2384 KB Output is correct
80 Partially correct 43 ms 2384 KB Partially correct - number of queries: 8230
81 Partially correct 45 ms 2760 KB Partially correct - number of queries: 8203
82 Partially correct 45 ms 2540 KB Partially correct - number of queries: 8111
83 Correct 3 ms 856 KB Output is correct
84 Partially correct 42 ms 2336 KB Partially correct - number of queries: 6786
85 Partially correct 44 ms 2484 KB Partially correct - number of queries: 8172
86 Correct 4 ms 344 KB Output is correct
87 Correct 4 ms 344 KB Output is correct
88 Correct 2 ms 344 KB Output is correct
89 Correct 4 ms 344 KB Output is correct
90 Correct 2 ms 344 KB Output is correct
91 Correct 3 ms 600 KB Output is correct
92 Correct 2 ms 596 KB Output is correct
93 Correct 6 ms 1112 KB Output is correct
94 Correct 4 ms 1112 KB Output is correct
95 Correct 5 ms 1112 KB Output is correct
96 Correct 6 ms 1112 KB Output is correct
97 Correct 4 ms 600 KB Output is correct