oj.uz

Submission #321601

# Submission time Handle Problem Language Result Execution time Memory
321601 2020-11-12T20:33:23 Z 12tqian The Big Prize (IOI17_prize) C++17
20 / 100
 209 ms 19564 KB 
#include "prize.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());

int find_best(int n) {
	int queries = 0;
	auto query = [&](int id) -> vector<int> {
		queries++;
		assert(queries <= 9990);
		return ask(id);
	};
    if (n <= 7) {
            for(int i = 0; i < n; i++) {
            std::vector<int> res = query(i);
            if(res[0] + res[1] == 0)
                return i;
        }
    }
    const int TIMES = 30;
    int lim  = 0;
    for (int i = 0; i < TIMES; i++) {
        vector<int> q = query(rng() % n);
        lim = max(lim, q[0] + q[1]);
    }
    Tree<int> rem; // not identified
    Tree<int> done;
    for (int i = 0; i < n; i++) {
        rem.insert(i);
    }
    while (true) {
        bool ok = false;
        int lo = 0;
        int hi = sz(rem) - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            int id = *rem.find_by_order(mid);
            vector<int> q = query(id);
            if (q[0] + q[1] == 0) {
                return id;
            } else if (q[0] + q[1] < lim) {
                rem.erase(id);
                done.insert(id);
                ok = true;
                break;
            } else {
                q[0] -= done.order_of_key(id);
                q[1] -= sz(done) - done.order_of_key(id);
				if (q[0] && q[1]) {
					if (q[0] > q[1]) hi = mid - 1;
					else lo = mid + 1;
				} else if (q[0]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
        if (ok) continue;
        int id = *rem.find_by_order(lo);
        vector<int> q = query(id);
        if (q[0] + q[1] < lim) {
            if (q[0] + q[1] == 0) {
                return id;
            } else {
                rem.erase(id);
                done.insert(id);
            }
        } else {
            id = *rem.find_by_order(hi);
            q = query(id);
            assert(q[0] + q[1] < lim);
            if (q[0] + q[1] == 0) {
                return id;
            } else {
                rem.erase(id);
                done.insert(id);
            }
        }
    }
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9708 KB Output is correct
2 Correct 112 ms 9708 KB Output is correct
3 Correct 116 ms 9708 KB Output is correct
4 Correct 110 ms 9808 KB Output is correct
5 Correct 109 ms 9840 KB Output is correct
6 Correct 111 ms 9708 KB Output is correct
7 Correct 108 ms 9852 KB Output is correct
8 Correct 109 ms 9708 KB Output is correct
9 Correct 110 ms 9708 KB Output is correct
10 Correct 119 ms 9796 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 9708 KB Output is correct
2 Correct 112 ms 9716 KB Output is correct
3 Correct 111 ms 9708 KB Output is correct
4 Correct 113 ms 9708 KB Output is correct
5 Correct 111 ms 9724 KB Output is correct
6 Correct 112 ms 9844 KB Output is correct
7 Correct 109 ms 9708 KB Output is correct
8 Correct 111 ms 9708 KB Output is correct
9 Correct 130 ms 9708 KB Output is correct
10 Correct 108 ms 9708 KB Output is correct
11 Correct 110 ms 9708 KB Output is correct
12 Correct 112 ms 9708 KB Output is correct
13 Correct 114 ms 9860 KB Output is correct
14 Correct 21 ms 1260 KB Output is correct
15 Partially correct 160 ms 9836 KB Partially correct - number of queries: 5293
16 Partially correct 160 ms 9708 KB Partially correct - number of queries: 5180
17 Partially correct 180 ms 9836 KB Partially correct - number of queries: 7902
18 Partially correct 192 ms 9708 KB Partially correct - number of queries: 7830
19 Partially correct 170 ms 9708 KB Partially correct - number of queries: 7356
20 Correct 60 ms 4972 KB Output is correct
21 Correct 130 ms 9836 KB Output is correct
22 Correct 157 ms 9844 KB Output is correct
23 Correct 114 ms 9708 KB Output is correct
24 Correct 116 ms 9708 KB Output is correct
25 Correct 117 ms 9836 KB Output is correct
26 Correct 116 ms 9708 KB Output is correct
27 Correct 112 ms 9708 KB Output is correct
28 Partially correct 181 ms 9708 KB Partially correct - number of queries: 7051
29 Correct 148 ms 9708 KB Output is correct
30 Partially correct 177 ms 9708 KB Partially correct - number of queries: 7785
31 Partially correct 172 ms 9708 KB Partially correct - number of queries: 7767
32 Correct 110 ms 9708 KB Output is correct
33 Correct 1 ms 380 KB Output is correct
34 Correct 140 ms 9708 KB Output is correct
35 Correct 111 ms 9708 KB Output is correct
36 Correct 147 ms 9708 KB Output is correct
37 Correct 116 ms 9704 KB Output is correct
38 Correct 110 ms 9708 KB Output is correct
39 Correct 121 ms 9836 KB Output is correct
40 Partially correct 175 ms 9708 KB Partially correct - number of queries: 6661
41 Correct 118 ms 9708 KB Output is correct
42 Correct 119 ms 9836 KB Output is correct
43 Correct 113 ms 9708 KB Output is correct
44 Correct 128 ms 9724 KB Output is correct
45 Correct 136 ms 9708 KB Output is correct
46 Partially correct 195 ms 9708 KB Partially correct - number of queries: 7893
47 Correct 115 ms 9708 KB Output is correct
48 Correct 137 ms 9852 KB Output is correct
49 Partially correct 176 ms 9708 KB Partially correct - number of queries: 6713
50 Partially correct 172 ms 9732 KB Partially correct - number of queries: 7861
51 Correct 127 ms 9708 KB Output is correct
52 Partially correct 182 ms 9708 KB Partially correct - number of queries: 7720
53 Correct 110 ms 9708 KB Output is correct
54 Correct 120 ms 9708 KB Output is correct
55 Partially correct 189 ms 9836 KB Partially correct - number of queries: 7871
56 Partially correct 203 ms 9708 KB Partially correct - number of queries: 7850
57 Correct 153 ms 9724 KB Output is correct
58 Correct 146 ms 9708 KB Output is correct
59 Correct 124 ms 9712 KB Output is correct
60 Correct 115 ms 9716 KB Output is correct
61 Correct 111 ms 9708 KB Output is correct
62 Correct 110 ms 9708 KB Output is correct
63 Correct 110 ms 9728 KB Output is correct
64 Correct 108 ms 9708 KB Output is correct
65 Correct 114 ms 9708 KB Output is correct
66 Correct 147 ms 9836 KB Output is correct
67 Correct 114 ms 9708 KB Output is correct
68 Correct 116 ms 9836 KB Output is correct
69 Correct 167 ms 9836 KB Output is correct
70 Correct 118 ms 9708 KB Output is correct
71 Partially correct 190 ms 9724 KB Partially correct - number of queries: 8508
72 Correct 117 ms 9708 KB Output is correct
73 Partially correct 194 ms 9708 KB Partially correct - number of queries: 8382
74 Partially correct 208 ms 9708 KB Partially correct - number of queries: 8454
75 Correct 112 ms 9880 KB Output is correct
76 Partially correct 185 ms 9708 KB Partially correct - number of queries: 7212
77 Partially correct 209 ms 9708 KB Partially correct - number of queries: 7980
78 Correct 116 ms 9708 KB Output is correct
79 Correct 145 ms 9708 KB Output is correct
80 Partially correct 196 ms 9756 KB Partially correct - number of queries: 7896
81 Partially correct 205 ms 9708 KB Partially correct - number of queries: 7965
82 Partially correct 190 ms 9708 KB Partially correct - number of queries: 7826
83 Correct 112 ms 9708 KB Output is correct
84 Partially correct 164 ms 9836 KB Partially correct - number of queries: 6514
85 Partially correct 198 ms 9708 KB Partially correct - number of queries: 7958
86 Runtime error 117 ms 19564 KB Execution killed with signal 6 (could be triggered by violating memory limits)
87 Halted 0 ms 0 KB -