oj.uz

Submission #33562

# Submission time Handle Problem Language Result Execution time Memory
33562 2017-10-30T07:01:44 Z top34051 The Big Prize (IOI17_prize) C++14
90 / 100
 66 ms 3772 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 200005;

int N, vmx;
bool vis[maxn];
pii ret[maxn];

pii talk(int pos) {
    pos = min(pos,N-1);
    if(!vis[pos]) {
        vis[pos] = 1;
        auto v = ask(pos);
        ret[pos] = {v[0],v[1]};
    }
    return ret[pos];
}

void solve(int l,int r) {
    if(l>r) return ;
    pii L, R;
    while(l<=r) {
        L = talk(l);
        if(L.X+L.Y==vmx) break;
        l++;
    }
    while(l<=r) {
        R = talk(r);
        if(R.X+R.Y==vmx) break;
        r--;
    }
    int mid = (l+r)/2;
    if(R.X-L.X>0) {
        solve(l,mid);
        solve(mid+1,r);
    }
}

int find_best(int n) {
    int i;
    pii res;
    N = n;
    //vmx
    for(i=0;i<min(N,730);i++) {
        res = talk(i);
        vmx = max(vmx,res.X+res.Y);
    }
//    printf("vmx = %d\n",vmx);
    //get all 1,2,...,v-1
    solve(0,N-1);
    for(i=0;i<N;i++) {
        if(vis[i] && ret[i].X+ret[i].Y!=vmx) {
//            printf("%d : {%d, %d}\n",i,ret[i].X,ret[i].Y);
            if(ret[i].X+ret[i].Y==0) return i;
        }
    }
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
20.0 / 20.0

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

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3772 KB Output is correct
2 Correct 3 ms 3772 KB Output is correct
3 Correct 6 ms 3772 KB Output is correct
4 Correct 0 ms 3772 KB Output is correct
5 Correct 3 ms 3772 KB Output is correct
6 Correct 6 ms 3772 KB Output is correct
7 Correct 3 ms 3772 KB Output is correct
8 Correct 0 ms 3772 KB Output is correct
9 Correct 3 ms 3772 KB Output is correct
10 Correct 3 ms 3772 KB Output is correct
11 Correct 9 ms 3772 KB Output is correct
12 Correct 6 ms 3772 KB Output is correct
13 Correct 3 ms 3772 KB Output is correct
14 Correct 3 ms 3772 KB Output is correct
15 Partially correct 16 ms 3772 KB Partially correct - number of queries: 7771
16 Partially correct 43 ms 3772 KB Partially correct - number of queries: 8186
17 Partially correct 23 ms 3772 KB Partially correct - number of queries: 8181
18 Partially correct 53 ms 3772 KB Partially correct - number of queries: 8233
19 Partially correct 39 ms 3772 KB Partially correct - number of queries: 7839
20 Partially correct 16 ms 3772 KB Partially correct - number of queries: 5518
21 Partially correct 23 ms 3772 KB Partially correct - number of queries: 8163
22 Partially correct 19 ms 3772 KB Partially correct - number of queries: 6498
23 Correct 6 ms 3772 KB Output is correct
24 Correct 6 ms 3772 KB Output is correct
25 Partially correct 49 ms 3772 KB Partially correct - number of queries: 7480
26 Partially correct 46 ms 3772 KB Partially correct - number of queries: 7376
27 Correct 0 ms 3772 KB Output is correct
28 Partially correct 26 ms 3772 KB Partially correct - number of queries: 7434
29 Partially correct 29 ms 3772 KB Partially correct - number of queries: 6391
30 Partially correct 46 ms 3772 KB Partially correct - number of queries: 8187
31 Partially correct 23 ms 3772 KB Partially correct - number of queries: 8110
32 Correct 9 ms 3772 KB Output is correct
33 Correct 0 ms 3772 KB Output is correct
34 Partially correct 43 ms 3772 KB Partially correct - number of queries: 8223
35 Correct 0 ms 3772 KB Output is correct
36 Partially correct 43 ms 3772 KB Partially correct - number of queries: 8266
37 Correct 0 ms 3772 KB Output is correct
38 Correct 9 ms 3772 KB Output is correct
39 Partially correct 26 ms 3772 KB Partially correct - number of queries: 8190
40 Partially correct 26 ms 3772 KB Partially correct - number of queries: 7225
41 Partially correct 33 ms 3772 KB Partially correct - number of queries: 8208
42 Partially correct 16 ms 3772 KB Partially correct - number of queries: 8208
43 Partially correct 29 ms 3772 KB Partially correct - number of queries: 8012
44 Partially correct 53 ms 3772 KB Partially correct - number of queries: 8184
45 Partially correct 46 ms 3772 KB Partially correct - number of queries: 7405
46 Partially correct 16 ms 3772 KB Partially correct - number of queries: 8226
47 Partially correct 39 ms 3772 KB Partially correct - number of queries: 7519
48 Partially correct 39 ms 3772 KB Partially correct - number of queries: 8190
49 Partially correct 56 ms 3772 KB Partially correct - number of queries: 8261
50 Partially correct 46 ms 3772 KB Partially correct - number of queries: 8194
51 Partially correct 26 ms 3772 KB Partially correct - number of queries: 8202
52 Partially correct 49 ms 3772 KB Partially correct - number of queries: 8258
53 Correct 3 ms 3772 KB Output is correct
54 Partially correct 39 ms 3772 KB Partially correct - number of queries: 8175
55 Partially correct 43 ms 3772 KB Partially correct - number of queries: 8236
56 Partially correct 16 ms 3772 KB Partially correct - number of queries: 8279
57 Partially correct 16 ms 3772 KB Partially correct - number of queries: 8215
58 Partially correct 36 ms 3772 KB Partially correct - number of queries: 8219
59 Partially correct 33 ms 3772 KB Partially correct - number of queries: 8250
60 Partially correct 33 ms 3772 KB Partially correct - number of queries: 8195
61 Correct 0 ms 3772 KB Output is correct
62 Correct 9 ms 3772 KB Output is correct
63 Correct 3 ms 3772 KB Output is correct
64 Correct 0 ms 3772 KB Output is correct
65 Correct 6 ms 3772 KB Output is correct
66 Correct 3 ms 3772 KB Output is correct
67 Correct 3 ms 3772 KB Output is correct
68 Correct 0 ms 3772 KB Output is correct
69 Correct 9 ms 3772 KB Output is correct
70 Correct 9 ms 3772 KB Output is correct
71 Partially correct 39 ms 3772 KB Partially correct - number of queries: 8831
72 Correct 0 ms 3772 KB Output is correct
73 Partially correct 39 ms 3772 KB Partially correct - number of queries: 8726
74 Partially correct 66 ms 3772 KB Partially correct - number of queries: 8771
75 Correct 0 ms 3772 KB Output is correct
76 Partially correct 26 ms 3772 KB Partially correct - number of queries: 7751
77 Partially correct 39 ms 3772 KB Partially correct - number of queries: 7883
78 Correct 9 ms 3772 KB Output is correct
79 Correct 16 ms 3772 KB Output is correct
80 Partially correct 33 ms 3772 KB Partially correct - number of queries: 7971
81 Partially correct 46 ms 3772 KB Partially correct - number of queries: 7997
82 Partially correct 39 ms 3772 KB Partially correct - number of queries: 7886
83 Correct 9 ms 3772 KB Output is correct
84 Partially correct 36 ms 3772 KB Partially correct - number of queries: 6724
85 Partially correct 36 ms 3772 KB Partially correct - number of queries: 7934
86 Correct 3 ms 3772 KB Output is correct
87 Correct 0 ms 3772 KB Output is correct
88 Correct 0 ms 3772 KB Output is correct
89 Correct 6 ms 3772 KB Output is correct
90 Correct 0 ms 3772 KB Output is correct
91 Correct 3 ms 3772 KB Output is correct
92 Correct 3 ms 3772 KB Output is correct
93 Correct 19 ms 3772 KB Output is correct
94 Correct 6 ms 3772 KB Output is correct
95 Correct 9 ms 3772 KB Output is correct
96 Correct 26 ms 3772 KB Output is correct
97 Correct 0 ms 3772 KB Output is correct