oj.uz

Submission #89167

# Submission time Handle Problem Language Result Execution time Memory
89167 2018-12-10T20:51:31 Z igzi The Big Prize (IOI17_prize) C++17
90 / 100
 109 ms 680 KB 
#include <bits/stdc++.h>
#include "prize.h"
#define maxN 200002
 
using namespace std;
 
int i,x=0;
vector <int> v,a;
 
int find_best(int n){
    for(i=0;i<n && i<500;i++){
    a=ask(i);
    if(a[0]+a[1]>x) x=a[0]+a[1];
    if(a[0]+a[1]==0) return i;
}
int p=-1;
for(int i=0;i<x;i++){
  int l,d,m;
  l=p+1; d=n-x+i;
  while(l<d){
    m=(l+d)/2;
    a=ask(m);
    if(a[0]+a[1]==x){
        if(a[0]-v.size()>0) d=m-1;
        else l=m+1;
    }
    else{
        d=m;
    }
  }
  v.push_back(l);
  p=l;
}
for(i=0;i<v.size();i++){
   a=ask(v[i]);
   if(a[0]+a[1]==0) return v[i];
}
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:34:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++){
         ~^~~~~~~~~
prize.cpp:38: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 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 4 ms 528 KB Output is correct
5 Correct 4 ms 528 KB Output is correct
6 Correct 5 ms 580 KB Output is correct
7 Correct 4 ms 580 KB Output is correct
8 Correct 7 ms 580 KB Output is correct
9 Correct 4 ms 580 KB Output is correct
10 Correct 8 ms 580 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 580 KB Output is correct
2 Correct 4 ms 580 KB Output is correct
3 Correct 8 ms 580 KB Output is correct
4 Correct 4 ms 580 KB Output is correct
5 Correct 4 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 7 ms 580 KB Output is correct
8 Correct 4 ms 580 KB Output is correct
9 Correct 4 ms 580 KB Output is correct
10 Correct 9 ms 580 KB Output is correct
11 Correct 6 ms 580 KB Output is correct
12 Correct 11 ms 580 KB Output is correct
13 Correct 11 ms 580 KB Output is correct
14 Correct 25 ms 580 KB Output is correct
15 Partially correct 75 ms 580 KB Partially correct - number of queries: 7562
16 Partially correct 75 ms 580 KB Partially correct - number of queries: 8261
17 Correct 3 ms 580 KB Output is correct
18 Partially correct 80 ms 580 KB Partially correct - number of queries: 8349
19 Correct 6 ms 580 KB Output is correct
20 Partially correct 44 ms 580 KB Partially correct - number of queries: 5366
21 Partially correct 45 ms 580 KB Partially correct - number of queries: 8011
22 Partially correct 64 ms 580 KB Partially correct - number of queries: 5953
23 Correct 4 ms 580 KB Output is correct
24 Correct 6 ms 580 KB Output is correct
25 Partially correct 45 ms 580 KB Partially correct - number of queries: 8130
26 Partially correct 77 ms 580 KB Partially correct - number of queries: 8090
27 Correct 8 ms 580 KB Output is correct
28 Partially correct 89 ms 580 KB Partially correct - number of queries: 8220
29 Partially correct 64 ms 580 KB Partially correct - number of queries: 6775
30 Partially correct 45 ms 580 KB Partially correct - number of queries: 8279
31 Correct 4 ms 580 KB Output is correct
32 Correct 11 ms 580 KB Output is correct
33 Correct 2 ms 580 KB Output is correct
34 Partially correct 36 ms 580 KB Partially correct - number of queries: 8024
35 Correct 5 ms 580 KB Output is correct
36 Partially correct 79 ms 580 KB Partially correct - number of queries: 7924
37 Correct 6 ms 580 KB Output is correct
38 Correct 8 ms 580 KB Output is correct
39 Partially correct 72 ms 580 KB Partially correct - number of queries: 8021
40 Partially correct 67 ms 580 KB Partially correct - number of queries: 7159
41 Partially correct 43 ms 580 KB Partially correct - number of queries: 8153
42 Partially correct 72 ms 580 KB Partially correct - number of queries: 8153
43 Partially correct 33 ms 580 KB Partially correct - number of queries: 7869
44 Partially correct 43 ms 580 KB Partially correct - number of queries: 8069
45 Partially correct 75 ms 580 KB Partially correct - number of queries: 8053
46 Correct 7 ms 580 KB Output is correct
47 Partially correct 84 ms 580 KB Partially correct - number of queries: 8159
48 Partially correct 77 ms 580 KB Partially correct - number of queries: 8204
49 Partially correct 32 ms 580 KB Partially correct - number of queries: 7905
50 Partially correct 80 ms 580 KB Partially correct - number of queries: 8353
51 Partially correct 72 ms 580 KB Partially correct - number of queries: 8056
52 Partially correct 77 ms 580 KB Partially correct - number of queries: 7879
53 Correct 4 ms 580 KB Output is correct
54 Partially correct 78 ms 580 KB Partially correct - number of queries: 8015
55 Correct 5 ms 580 KB Output is correct
56 Partially correct 76 ms 580 KB Partially correct - number of queries: 8348
57 Partially correct 63 ms 580 KB Partially correct - number of queries: 8148
58 Partially correct 79 ms 580 KB Partially correct - number of queries: 8220
59 Partially correct 70 ms 580 KB Partially correct - number of queries: 8152
60 Partially correct 36 ms 580 KB Partially correct - number of queries: 8048
61 Correct 7 ms 580 KB Output is correct
62 Correct 8 ms 580 KB Output is correct
63 Correct 7 ms 580 KB Output is correct
64 Correct 7 ms 580 KB Output is correct
65 Correct 12 ms 580 KB Output is correct
66 Correct 5 ms 580 KB Output is correct
67 Correct 4 ms 580 KB Output is correct
68 Correct 6 ms 580 KB Output is correct
69 Correct 7 ms 580 KB Output is correct
70 Correct 8 ms 580 KB Output is correct
71 Partially correct 55 ms 580 KB Partially correct - number of queries: 8305
72 Correct 14 ms 580 KB Output is correct
73 Partially correct 79 ms 580 KB Partially correct - number of queries: 8185
74 Partially correct 92 ms 580 KB Partially correct - number of queries: 8240
75 Correct 9 ms 580 KB Output is correct
76 Partially correct 71 ms 580 KB Partially correct - number of queries: 7154
77 Partially correct 80 ms 580 KB Partially correct - number of queries: 8378
78 Correct 12 ms 580 KB Output is correct
79 Correct 40 ms 580 KB Output is correct
80 Partially correct 78 ms 580 KB Partially correct - number of queries: 8346
81 Partially correct 75 ms 580 KB Partially correct - number of queries: 8346
82 Partially correct 109 ms 580 KB Partially correct - number of queries: 8310
83 Correct 8 ms 580 KB Output is correct
84 Partially correct 67 ms 580 KB Partially correct - number of queries: 6944
85 Partially correct 79 ms 580 KB Partially correct - number of queries: 8371
86 Partially correct 39 ms 584 KB Partially correct - number of queries: 9465
87 Correct 13 ms 584 KB Output is correct
88 Partially correct 56 ms 584 KB Partially correct - number of queries: 8952
89 Partially correct 98 ms 584 KB Partially correct - number of queries: 9389
90 Correct 7 ms 584 KB Output is correct
91 Partially correct 51 ms 584 KB Partially correct - number of queries: 5665
92 Partially correct 93 ms 680 KB Partially correct - number of queries: 8990
93 Partially correct 79 ms 680 KB Partially correct - number of queries: 9415
94 Partially correct 77 ms 680 KB Partially correct - number of queries: 9416
95 Partially correct 59 ms 680 KB Partially correct - number of queries: 9406
96 Partially correct 73 ms 680 KB Partially correct - number of queries: 9337
97 Partially correct 94 ms 680 KB Partially correct - number of queries: 8990