oj.uz

Submission #162332

# Submission time Handle Problem Language Result Execution time Memory
162332 2019-11-07T15:15:35 Z popovicirobert The Big Prize (IOI17_prize) C++14
20 / 100
 137 ms 508 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int find_best(int n) {
    srand(time(NULL));

    auto myrand = [&]() {
        return (1LL * (1LL << 15) * rand() ^ rand()) % n;
    };

    vector <bool> vis(n);
    int i, mx = 0;

    for(i = 0; i < 15 && i < n; i++) {
        int cur = myrand();
        while(vis[cur]) {
            cur = myrand();
        }
        vector <int> a = ask(cur);
        mx = max(mx, a[0] + a[1]);
        vis[cur] = 1;
    }

    int num = n - mx;
    i = 0;
    while(i < n) {
        vector <int> a = ask(i);
        if(a[0] + a[1] == 0) {
            return i;
        }
        if(a[0] + a[1] < mx) {
            while(1) {
                a = ask(++i);
                if(a[0] + a[1] == 0) {
                    return i;
                }
                if(a[0] + a[1] == mx) break;
            }
        }
        else {
            int l = a[0], r = a[1];
            int res = 0;
            for(int step = 1 << 17; step; step >>= 1) {
                if(i + res + step < n && num >= res + step + 1) {
                    a = ask(i + res + step);
                    if(a[0] == l && a[1] == r) {
                        res += step;
                    }
                }
            }
            i += res + 1;
            num -= (res + 1);
        }
    }

    assert(0);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 312 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 312 KB Output is correct
5 Correct 3 ms 248 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 424 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 252 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 276 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 6 ms 248 KB Output is correct
12 Correct 3 ms 304 KB Output is correct
13 Correct 7 ms 248 KB Output is correct
14 Correct 7 ms 248 KB Output is correct
15 Correct 15 ms 248 KB Output is correct
16 Partially correct 76 ms 376 KB Partially correct - number of queries: 7924
17 Correct 2 ms 248 KB Output is correct
18 Partially correct 107 ms 376 KB Partially correct - number of queries: 9320
19 Correct 2 ms 248 KB Output is correct
20 Correct 13 ms 376 KB Output is correct
21 Correct 18 ms 308 KB Output is correct
22 Correct 8 ms 248 KB Output is correct
23 Correct 3 ms 248 KB Output is correct
24 Correct 2 ms 392 KB Output is correct
25 Partially correct 48 ms 248 KB Partially correct - number of queries: 5252
26 Partially correct 54 ms 248 KB Partially correct - number of queries: 5167
27 Correct 3 ms 248 KB Output is correct
28 Partially correct 86 ms 404 KB Partially correct - number of queries: 8842
29 Partially correct 53 ms 248 KB Partially correct - number of queries: 6696
30 Partially correct 88 ms 248 KB Partially correct - number of queries: 9242
31 Correct 2 ms 248 KB Output is correct
32 Correct 4 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 28 ms 248 KB Output is correct
35 Correct 3 ms 308 KB Output is correct
36 Correct 12 ms 424 KB Output is correct
37 Correct 4 ms 276 KB Output is correct
38 Correct 3 ms 376 KB Output is correct
39 Correct 65 ms 248 KB Output is correct
40 Partially correct 123 ms 304 KB Partially correct - number of queries: 7901
41 Partially correct 57 ms 276 KB Partially correct - number of queries: 5557
42 Partially correct 28 ms 308 KB Partially correct - number of queries: 5557
43 Partially correct 44 ms 248 KB Partially correct - number of queries: 5012
44 Correct 50 ms 376 KB Output is correct
45 Correct 29 ms 248 KB Output is correct
46 Correct 3 ms 248 KB Output is correct
47 Correct 41 ms 504 KB Output is correct
48 Partially correct 76 ms 248 KB Partially correct - number of queries: 6879
49 Correct 5 ms 376 KB Output is correct
50 Partially correct 88 ms 248 KB Partially correct - number of queries: 9320
51 Correct 20 ms 404 KB Output is correct
52 Correct 3 ms 392 KB Output is correct
53 Correct 3 ms 508 KB Output is correct
54 Correct 24 ms 396 KB Output is correct
55 Correct 3 ms 376 KB Output is correct
56 Partially correct 81 ms 248 KB Partially correct - number of queries: 9320
57 Partially correct 65 ms 248 KB Partially correct - number of queries: 6782
58 Partially correct 43 ms 376 KB Partially correct - number of queries: 6901
59 Partially correct 56 ms 304 KB Partially correct - number of queries: 5557
60 Partially correct 48 ms 376 KB Partially correct - number of queries: 5155
61 Correct 3 ms 376 KB Output is correct
62 Correct 2 ms 380 KB Output is correct
63 Correct 5 ms 380 KB Output is correct
64 Correct 3 ms 376 KB Output is correct
65 Correct 3 ms 248 KB Output is correct
66 Correct 6 ms 248 KB Output is correct
67 Correct 2 ms 248 KB Output is correct
68 Correct 4 ms 424 KB Output is correct
69 Correct 7 ms 248 KB Output is correct
70 Correct 2 ms 376 KB Output is correct
71 Partially correct 92 ms 296 KB Partially correct - number of queries: 9307
72 Correct 8 ms 248 KB Output is correct
73 Partially correct 99 ms 248 KB Partially correct - number of queries: 9169
74 Partially correct 84 ms 248 KB Partially correct - number of queries: 9228
75 Correct 5 ms 376 KB Output is correct
76 Partially correct 75 ms 248 KB Partially correct - number of queries: 7893
77 Partially correct 59 ms 248 KB Partially correct - number of queries: 9315
78 Correct 9 ms 248 KB Output is correct
79 Correct 51 ms 248 KB Output is correct
80 Partially correct 137 ms 376 KB Partially correct - number of queries: 9315
81 Partially correct 48 ms 504 KB Partially correct - number of queries: 9315
82 Partially correct 79 ms 312 KB Partially correct - number of queries: 9233
83 Correct 4 ms 376 KB Output is correct
84 Partially correct 93 ms 248 KB Partially correct - number of queries: 7585
85 Partially correct 94 ms 248 KB Partially correct - number of queries: 9216
86 Incorrect 108 ms 248 KB Incorrect
87 Halted 0 ms 0 KB -