oj.uz

Submission #89168

# Submission time Handle Problem Language Result Execution time Memory
89168 2018-12-10T20:59:25 Z igzi The Big Prize (IOI17_prize) C++17
90 / 100
 96 ms 5628 KB 
#include <bits/stdc++.h>
#include "prize.h"
#define maxN 200002
 
using namespace std;
 
int i,x=0;
vector <int> v,a[maxN];
 
int find_best(int n){
    for(i=0;i<n && i<500;i++){
    if(a[i].empty()) a[i]=ask(i);
    if(a[i][0]+a[i][1]>x) x=a[i][0]+a[i][1];
    if(a[i][0]+a[i][1]==0) return i;
}
int p=-1;
for(int i=0;i<x;i++){
  int l,d,m;
  l=p+1; d=n-1;
  while(l<d){
    m=(l+d)/2;
    if(a[m].empty()) a[m]=ask(m);
    if(a[m][0]+a[m][1]==x){
        if(a[m][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++){
   if(a[v[i]].empty()) a[v[i]]=ask(v[i]);
   if(a[v[i]][0]+a[v[i]][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 8 ms 5128 KB Output is correct
2 Correct 13 ms 5128 KB Output is correct
3 Correct 12 ms 5128 KB Output is correct
4 Correct 9 ms 5156 KB Output is correct
5 Correct 13 ms 5232 KB Output is correct
6 Correct 6 ms 5256 KB Output is correct
7 Correct 11 ms 5256 KB Output is correct
8 Correct 11 ms 5256 KB Output is correct
9 Correct 13 ms 5256 KB Output is correct
10 Correct 13 ms 5256 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5268 KB Output is correct
2 Correct 11 ms 5268 KB Output is correct
3 Correct 10 ms 5268 KB Output is correct
4 Correct 11 ms 5268 KB Output is correct
5 Correct 8 ms 5324 KB Output is correct
6 Correct 6 ms 5324 KB Output is correct
7 Correct 11 ms 5324 KB Output is correct
8 Correct 10 ms 5324 KB Output is correct
9 Correct 8 ms 5324 KB Output is correct
10 Correct 12 ms 5324 KB Output is correct
11 Correct 18 ms 5324 KB Output is correct
12 Correct 17 ms 5324 KB Output is correct
13 Correct 16 ms 5324 KB Output is correct
14 Correct 29 ms 5436 KB Output is correct
15 Partially correct 67 ms 5436 KB Partially correct - number of queries: 7441
16 Partially correct 40 ms 5500 KB Partially correct - number of queries: 7980
17 Correct 10 ms 5500 KB Output is correct
18 Partially correct 78 ms 5500 KB Partially correct - number of queries: 8014
19 Correct 10 ms 5500 KB Output is correct
20 Partially correct 63 ms 5500 KB Partially correct - number of queries: 5228
21 Partially correct 94 ms 5500 KB Partially correct - number of queries: 7780
22 Partially correct 78 ms 5564 KB Partially correct - number of queries: 5908
23 Correct 11 ms 5564 KB Output is correct
24 Correct 16 ms 5564 KB Output is correct
25 Partially correct 77 ms 5564 KB Partially correct - number of queries: 7846
26 Partially correct 77 ms 5580 KB Partially correct - number of queries: 7849
27 Correct 9 ms 5580 KB Output is correct
28 Partially correct 96 ms 5580 KB Partially correct - number of queries: 7847
29 Partially correct 47 ms 5580 KB Partially correct - number of queries: 6474
30 Partially correct 89 ms 5580 KB Partially correct - number of queries: 7952
31 Correct 11 ms 5580 KB Output is correct
32 Correct 11 ms 5580 KB Output is correct
33 Correct 6 ms 5580 KB Output is correct
34 Partially correct 67 ms 5580 KB Partially correct - number of queries: 7850
35 Correct 10 ms 5580 KB Output is correct
36 Partially correct 42 ms 5580 KB Partially correct - number of queries: 7765
37 Correct 16 ms 5580 KB Output is correct
38 Correct 13 ms 5580 KB Output is correct
39 Partially correct 85 ms 5580 KB Partially correct - number of queries: 7852
40 Partially correct 70 ms 5580 KB Partially correct - number of queries: 6882
41 Partially correct 80 ms 5580 KB Partially correct - number of queries: 7841
42 Partially correct 40 ms 5580 KB Partially correct - number of queries: 7841
43 Partially correct 58 ms 5580 KB Partially correct - number of queries: 7458
44 Partially correct 80 ms 5580 KB Partially correct - number of queries: 7883
45 Partially correct 75 ms 5604 KB Partially correct - number of queries: 7839
46 Correct 8 ms 5604 KB Output is correct
47 Partially correct 59 ms 5604 KB Partially correct - number of queries: 7927
48 Partially correct 81 ms 5604 KB Partially correct - number of queries: 7958
49 Partially correct 39 ms 5604 KB Partially correct - number of queries: 7812
50 Partially correct 60 ms 5604 KB Partially correct - number of queries: 8016
51 Partially correct 39 ms 5604 KB Partially correct - number of queries: 7869
52 Partially correct 65 ms 5604 KB Partially correct - number of queries: 7803
53 Correct 8 ms 5604 KB Output is correct
54 Partially correct 69 ms 5604 KB Partially correct - number of queries: 7833
55 Correct 7 ms 5604 KB Output is correct
56 Partially correct 54 ms 5604 KB Partially correct - number of queries: 8010
57 Partially correct 69 ms 5604 KB Partially correct - number of queries: 7872
58 Partially correct 80 ms 5604 KB Partially correct - number of queries: 7915
59 Partially correct 73 ms 5604 KB Partially correct - number of queries: 7828
60 Partially correct 82 ms 5604 KB Partially correct - number of queries: 7460
61 Correct 8 ms 5604 KB Output is correct
62 Correct 12 ms 5604 KB Output is correct
63 Correct 13 ms 5604 KB Output is correct
64 Correct 9 ms 5604 KB Output is correct
65 Correct 14 ms 5604 KB Output is correct
66 Correct 10 ms 5604 KB Output is correct
67 Correct 10 ms 5604 KB Output is correct
68 Correct 9 ms 5604 KB Output is correct
69 Correct 16 ms 5604 KB Output is correct
70 Correct 13 ms 5604 KB Output is correct
71 Partially correct 94 ms 5604 KB Partially correct - number of queries: 8270
72 Correct 10 ms 5604 KB Output is correct
73 Partially correct 76 ms 5604 KB Partially correct - number of queries: 8159
74 Partially correct 87 ms 5604 KB Partially correct - number of queries: 8219
75 Correct 12 ms 5604 KB Output is correct
76 Partially correct 82 ms 5604 KB Partially correct - number of queries: 7113
77 Partially correct 90 ms 5604 KB Partially correct - number of queries: 8011
78 Correct 19 ms 5604 KB Output is correct
79 Correct 27 ms 5604 KB Output is correct
80 Partially correct 41 ms 5604 KB Partially correct - number of queries: 8027
81 Partially correct 64 ms 5604 KB Partially correct - number of queries: 8052
82 Partially correct 87 ms 5628 KB Partially correct - number of queries: 7977
83 Correct 12 ms 5628 KB Output is correct
84 Partially correct 68 ms 5628 KB Partially correct - number of queries: 6639
85 Partially correct 49 ms 5628 KB Partially correct - number of queries: 8050
86 Correct 51 ms 5628 KB Output is correct
87 Correct 16 ms 5628 KB Output is correct
88 Correct 44 ms 5628 KB Output is correct
89 Correct 45 ms 5628 KB Output is correct
90 Correct 12 ms 5628 KB Output is correct
91 Correct 30 ms 5628 KB Output is correct
92 Correct 22 ms 5628 KB Output is correct
93 Correct 24 ms 5628 KB Output is correct
94 Correct 31 ms 5628 KB Output is correct
95 Correct 45 ms 5628 KB Output is correct
96 Correct 43 ms 5628 KB Output is correct
97 Correct 45 ms 5628 KB Output is correct