oj.uz

Submission #33561

# Submission time Handle Problem Language Result Execution time Memory
33561 2017-10-30T06:52:49 Z top34051 The Big Prize (IOI17_prize) C++14
20 / 100
 66 ms 3784 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<sqrt(N);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 3784 KB Output is correct
2 Correct 0 ms 3784 KB Output is correct
3 Correct 3 ms 3784 KB Output is correct
4 Correct 0 ms 3784 KB Output is correct
5 Correct 6 ms 3784 KB Output is correct
6 Correct 3 ms 3784 KB Output is correct
7 Correct 3 ms 3784 KB Output is correct
8 Correct 6 ms 3784 KB Output is correct
9 Correct 6 ms 3784 KB Output is correct
10 Correct 3 ms 3784 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3784 KB Output is correct
2 Correct 0 ms 3784 KB Output is correct
3 Correct 19 ms 3784 KB Output is correct
4 Correct 0 ms 3784 KB Output is correct
5 Correct 6 ms 3784 KB Output is correct
6 Correct 0 ms 3784 KB Output is correct
7 Correct 0 ms 3784 KB Output is correct
8 Correct 0 ms 3784 KB Output is correct
9 Correct 0 ms 3784 KB Output is correct
10 Correct 0 ms 3784 KB Output is correct
11 Correct 0 ms 3784 KB Output is correct
12 Correct 6 ms 3784 KB Output is correct
13 Correct 0 ms 3784 KB Output is correct
14 Correct 13 ms 3784 KB Output is correct
15 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7497
16 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7908
17 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7903
18 Partially correct 49 ms 3784 KB Partially correct - number of queries: 7955
19 Partially correct 53 ms 3784 KB Partially correct - number of queries: 7568
20 Partially correct 9 ms 3784 KB Partially correct - number of queries: 5126
21 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7885
22 Partially correct 6 ms 3784 KB Partially correct - number of queries: 6231
23 Correct 6 ms 3784 KB Output is correct
24 Correct 6 ms 3784 KB Output is correct
25 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7209
26 Partially correct 59 ms 3784 KB Partially correct - number of queries: 7109
27 Correct 3 ms 3784 KB Output is correct
28 Partially correct 36 ms 3784 KB Partially correct - number of queries: 7174
29 Partially correct 23 ms 3784 KB Partially correct - number of queries: 6118
30 Partially correct 16 ms 3784 KB Partially correct - number of queries: 7909
31 Partially correct 19 ms 3784 KB Partially correct - number of queries: 7832
32 Correct 3 ms 3784 KB Output is correct
33 Correct 0 ms 3784 KB Output is correct
34 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7945
35 Correct 9 ms 3784 KB Output is correct
36 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7988
37 Correct 3 ms 3784 KB Output is correct
38 Correct 6 ms 3784 KB Output is correct
39 Partially correct 33 ms 3784 KB Partially correct - number of queries: 7912
40 Partially correct 33 ms 3784 KB Partially correct - number of queries: 6958
41 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7930
42 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7930
43 Partially correct 19 ms 3784 KB Partially correct - number of queries: 7734
44 Partially correct 53 ms 3784 KB Partially correct - number of queries: 7906
45 Partially correct 16 ms 3784 KB Partially correct - number of queries: 7123
46 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7948
47 Partially correct 36 ms 3784 KB Partially correct - number of queries: 7241
48 Partially correct 39 ms 3784 KB Partially correct - number of queries: 7912
49 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7983
50 Partially correct 13 ms 3784 KB Partially correct - number of queries: 7916
51 Partially correct 23 ms 3784 KB Partially correct - number of queries: 7924
52 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7980
53 Correct 3 ms 3784 KB Output is correct
54 Partially correct 23 ms 3784 KB Partially correct - number of queries: 7897
55 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7958
56 Partially correct 36 ms 3784 KB Partially correct - number of queries: 8001
57 Partially correct 26 ms 3784 KB Partially correct - number of queries: 7937
58 Partially correct 43 ms 3784 KB Partially correct - number of queries: 7941
59 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7972
60 Partially correct 23 ms 3784 KB Partially correct - number of queries: 7917
61 Correct 0 ms 3784 KB Output is correct
62 Correct 13 ms 3784 KB Output is correct
63 Correct 0 ms 3784 KB Output is correct
64 Correct 3 ms 3784 KB Output is correct
65 Correct 0 ms 3784 KB Output is correct
66 Correct 9 ms 3784 KB Output is correct
67 Correct 16 ms 3784 KB Output is correct
68 Correct 0 ms 3784 KB Output is correct
69 Correct 3 ms 3784 KB Output is correct
70 Correct 6 ms 3784 KB Output is correct
71 Partially correct 26 ms 3784 KB Partially correct - number of queries: 8549
72 Correct 6 ms 3784 KB Output is correct
73 Partially correct 23 ms 3784 KB Partially correct - number of queries: 8444
74 Partially correct 46 ms 3784 KB Partially correct - number of queries: 8489
75 Correct 6 ms 3784 KB Output is correct
76 Partially correct 66 ms 3784 KB Partially correct - number of queries: 7469
77 Partially correct 19 ms 3784 KB Partially correct - number of queries: 7679
78 Correct 6 ms 3784 KB Output is correct
79 Correct 23 ms 3784 KB Output is correct
80 Partially correct 46 ms 3784 KB Partially correct - number of queries: 7623
81 Partially correct 19 ms 3784 KB Partially correct - number of queries: 7701
82 Partially correct 29 ms 3784 KB Partially correct - number of queries: 7699
83 Correct 3 ms 3784 KB Output is correct
84 Partially correct 66 ms 3784 KB Partially correct - number of queries: 6521
85 Partially correct 36 ms 3784 KB Partially correct - number of queries: 7644
86 Incorrect 29 ms 3784 KB Incorrect
87 Halted 0 ms 0 KB -