oj.uz

Submission #790809

# Submission time Handle Problem Language Result Execution time Memory
790809 2023-07-23T08:10:31 Z peteza The Big Prize (IOI17_prize) C++14
90 / 100
 81 ms 696 KB 
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

bool vis[200005];

int find_best(int n) {
    if(n == 1) return 0;
    int mx = -1, ci;
    int c0, c1;
    for(int i=0;i<min(n, 500);i++) {
        auto e = ask(i);
        if(e[0] + e[1] > mx) {
            c0 = e[0], c1=e[1];
            mx = e[0] + e[1]; ci = i;
        } 
    }
    //start at ci
    int l, r, mid;
    while(1) {
        l = ci; r = n-1;
        while(l<=r) {
            mid = (l+r) >> 1;
            auto e = ask(mid);
            if(e[0] + e[1] != mx) r = mid-1;
            else if(e[0] == c0) l = mid+1;
            else r = mid - 1;
        }
        for(int i=ci;i<l;i++) 
            vis[i] = 1;
        if(l >= n-1) break;
        ci = l; auto e = ask(ci);
        while(ci < n && e[0] + e[1] != mx) {
            if(ci >= n-1) break;
            e = ask(++ci);
            c0 = e[0]; c1 = e[1];
        }
        if(ci >= n-1) break;
    }
    for(int i=0;i<n;i++) {
        if(vis[i]) continue;
        auto e = ask(i);
        if(e[0] + e[1] == 0) return i;
    }
    return 0;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:10:13: warning: variable 'c1' set but not used [-Wunused-but-set-variable]
   10 |     int c0, c1;
      |             ^~
prize.cpp:26:18: warning: 'c0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |             else if(e[0] == c0) l = mid+1;
      |                  ^~
prize.cpp:23:21: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |             mid = (l+r) >> 1;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 464 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 4 ms 424 KB Output is correct
7 Correct 5 ms 436 KB Output is correct
8 Correct 4 ms 432 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 4 ms 432 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 464 KB Output is correct
2 Correct 6 ms 456 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 3 ms 424 KB Output is correct
6 Correct 2 ms 432 KB Output is correct
7 Correct 5 ms 428 KB Output is correct
8 Correct 5 ms 436 KB Output is correct
9 Correct 5 ms 464 KB Output is correct
10 Correct 4 ms 436 KB Output is correct
11 Correct 9 ms 456 KB Output is correct
12 Correct 9 ms 456 KB Output is correct
13 Correct 5 ms 484 KB Output is correct
14 Correct 21 ms 296 KB Output is correct
15 Partially correct 41 ms 452 KB Partially correct - number of queries: 8733
16 Partially correct 74 ms 456 KB Partially correct - number of queries: 9508
17 Partially correct 44 ms 696 KB Partially correct - number of queries: 9131
18 Partially correct 67 ms 416 KB Partially correct - number of queries: 9594
19 Partially correct 59 ms 452 KB Partially correct - number of queries: 8569
20 Partially correct 41 ms 348 KB Partially correct - number of queries: 6218
21 Partially correct 62 ms 452 KB Partially correct - number of queries: 9218
22 Partially correct 57 ms 468 KB Partially correct - number of queries: 6890
23 Correct 3 ms 440 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Partially correct 54 ms 476 KB Partially correct - number of queries: 9368
26 Partially correct 70 ms 472 KB Partially correct - number of queries: 9282
27 Correct 3 ms 436 KB Output is correct
28 Partially correct 81 ms 456 KB Partially correct - number of queries: 9437
29 Partially correct 33 ms 576 KB Partially correct - number of queries: 7755
30 Partially correct 50 ms 440 KB Partially correct - number of queries: 9513
31 Partially correct 32 ms 468 KB Partially correct - number of queries: 9037
32 Correct 11 ms 412 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 70 ms 364 KB Partially correct - number of queries: 9266
35 Correct 5 ms 448 KB Output is correct
36 Partially correct 63 ms 456 KB Partially correct - number of queries: 9173
37 Correct 6 ms 436 KB Output is correct
38 Correct 6 ms 464 KB Output is correct
39 Partially correct 65 ms 448 KB Partially correct - number of queries: 9247
40 Partially correct 79 ms 472 KB Partially correct - number of queries: 8200
41 Partially correct 72 ms 428 KB Partially correct - number of queries: 9382
42 Partially correct 71 ms 472 KB Partially correct - number of queries: 9382
43 Partially correct 56 ms 416 KB Partially correct - number of queries: 9089
44 Partially correct 32 ms 528 KB Partially correct - number of queries: 9309
45 Partially correct 62 ms 616 KB Partially correct - number of queries: 9290
46 Partially correct 30 ms 488 KB Partially correct - number of queries: 9136
47 Partially correct 73 ms 424 KB Partially correct - number of queries: 9372
48 Partially correct 72 ms 636 KB Partially correct - number of queries: 9457
49 Partially correct 39 ms 420 KB Partially correct - number of queries: 9154
50 Partially correct 32 ms 472 KB Partially correct - number of queries: 9588
51 Partially correct 31 ms 476 KB Partially correct - number of queries: 9324
52 Partially correct 58 ms 492 KB Partially correct - number of queries: 9121
53 Correct 5 ms 464 KB Output is correct
54 Partially correct 34 ms 476 KB Partially correct - number of queries: 9249
55 Partially correct 48 ms 440 KB Partially correct - number of queries: 9121
56 Partially correct 56 ms 364 KB Partially correct - number of queries: 9587
57 Partially correct 31 ms 468 KB Partially correct - number of queries: 9377
58 Partially correct 33 ms 488 KB Partially correct - number of queries: 9456
59 Partially correct 46 ms 424 KB Partially correct - number of queries: 9383
60 Partially correct 68 ms 592 KB Partially correct - number of queries: 9288
61 Correct 3 ms 436 KB Output is correct
62 Correct 4 ms 432 KB Output is correct
63 Correct 4 ms 472 KB Output is correct
64 Correct 3 ms 432 KB Output is correct
65 Correct 5 ms 420 KB Output is correct
66 Correct 10 ms 412 KB Output is correct
67 Correct 6 ms 428 KB Output is correct
68 Correct 6 ms 424 KB Output is correct
69 Correct 13 ms 416 KB Output is correct
70 Correct 6 ms 424 KB Output is correct
71 Partially correct 59 ms 444 KB Partially correct - number of queries: 9715
72 Correct 7 ms 432 KB Output is correct
73 Partially correct 64 ms 444 KB Partially correct - number of queries: 9577
74 Partially correct 47 ms 468 KB Partially correct - number of queries: 9658
75 Correct 4 ms 440 KB Output is correct
76 Partially correct 72 ms 468 KB Partially correct - number of queries: 8339
77 Partially correct 64 ms 476 KB Partially correct - number of queries: 9492
78 Correct 7 ms 404 KB Output is correct
79 Correct 44 ms 392 KB Output is correct
80 Partially correct 36 ms 404 KB Partially correct - number of queries: 9594
81 Partially correct 62 ms 444 KB Partially correct - number of queries: 9562
82 Partially correct 64 ms 456 KB Partially correct - number of queries: 9526
83 Correct 3 ms 368 KB Output is correct
84 Partially correct 33 ms 412 KB Partially correct - number of queries: 7935
85 Partially correct 57 ms 448 KB Partially correct - number of queries: 9620
86 Correct 8 ms 464 KB Output is correct
87 Correct 4 ms 432 KB Output is correct
88 Correct 6 ms 432 KB Output is correct
89 Correct 7 ms 464 KB Output is correct
90 Correct 5 ms 428 KB Output is correct
91 Correct 9 ms 424 KB Output is correct
92 Correct 6 ms 464 KB Output is correct
93 Correct 13 ms 464 KB Output is correct
94 Correct 14 ms 380 KB Output is correct
95 Correct 12 ms 468 KB Output is correct
96 Correct 10 ms 464 KB Output is correct
97 Correct 9 ms 464 KB Output is correct