oj.uz

Submission #100711

# Submission time Handle Problem Language Result Execution time Memory
100711 2019-03-13T15:06:42 Z Bodo171 The Big Prize (IOI17_prize) C++14
90 / 100
 101 ms 6176 KB 
#include "prize.h"
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
const int prdf=500;//modifici dupa asta
int lg[nmax];
int spec[nmax];
int mx,nr,i;
vector<int> v[nmax];
int cate_st(int poz)
{
    if(v[poz].empty()) v[poz]=ask(poz);
    return v[poz][0];
}
int cate(int poz)
{
    if(v[poz].empty()) v[poz]=ask(poz);
    return (v[poz][0]+v[poz][1]);
}
void solve(int st,int dr)
{
    int len=spec[dr]-spec[st];
    int poz=spec[st];
    for(int p=lg[len];p>=0;p--)
    {
        if(poz+(1<<p)<spec[dr])
     {
        if(cate_st(poz+(1<<p))==st&&cate(poz+(1<<p))==mx)
            poz+=(1<<p);
     }
    }
    poz++;spec[st+1]=poz;
}
int find_best(int n) {
    for(i=2;i<=n+1;i++)
        lg[i]=lg[i/2]+1;
    for(i=0;i<min(prdf,n);i++)
    {
        v[i]=ask(i);
        if(v[i][0]+v[i][1]>mx)
            mx=v[i][0]+v[i][1];
    }
    spec[0]=-1;
    for(i=0;i<min(prdf,n);i++)
    {
        if(v[i][0]+v[i][1]!=mx)
            spec[++nr]=i;
    }
    spec[mx+1]=n;
    for(int i=nr;i<mx;i++)
        {
             solve(i,mx+1);
        }
    for(i=1;i<=mx;i++)
        if(cate(spec[i])==0)
           return spec[i];
	return 0;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:56:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1;i<=mx;i++)
     ^~~
prize.cpp:59:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return 0;
  ^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5780 KB Output is correct
2 Correct 8 ms 5908 KB Output is correct
3 Correct 11 ms 5752 KB Output is correct
4 Correct 12 ms 5880 KB Output is correct
5 Correct 14 ms 5880 KB Output is correct
6 Correct 12 ms 5800 KB Output is correct
7 Correct 11 ms 5800 KB Output is correct
8 Correct 12 ms 5880 KB Output is correct
9 Correct 14 ms 5800 KB Output is correct
10 Correct 13 ms 5892 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5760 KB Output is correct
2 Correct 12 ms 5808 KB Output is correct
3 Correct 9 ms 5808 KB Output is correct
4 Correct 14 ms 5880 KB Output is correct
5 Correct 12 ms 5804 KB Output is correct
6 Correct 9 ms 5888 KB Output is correct
7 Correct 11 ms 5888 KB Output is correct
8 Correct 14 ms 5880 KB Output is correct
9 Correct 13 ms 5708 KB Output is correct
10 Correct 12 ms 5900 KB Output is correct
11 Correct 16 ms 5776 KB Output is correct
12 Correct 19 ms 5824 KB Output is correct
13 Correct 15 ms 5800 KB Output is correct
14 Correct 22 ms 5120 KB Output is correct
15 Partially correct 60 ms 6060 KB Partially correct - number of queries: 7938
16 Partially correct 101 ms 6000 KB Partially correct - number of queries: 8356
17 Partially correct 71 ms 6008 KB Partially correct - number of queries: 8353
18 Partially correct 54 ms 6176 KB Partially correct - number of queries: 8357
19 Partially correct 71 ms 6116 KB Partially correct - number of queries: 7834
20 Partially correct 48 ms 5576 KB Partially correct - number of queries: 5531
21 Partially correct 64 ms 6008 KB Partially correct - number of queries: 8259
22 Partially correct 50 ms 6020 KB Partially correct - number of queries: 6281
23 Correct 14 ms 5812 KB Output is correct
24 Correct 17 ms 5880 KB Output is correct
25 Partially correct 72 ms 6000 KB Partially correct - number of queries: 8241
26 Partially correct 61 ms 6048 KB Partially correct - number of queries: 8249
27 Correct 16 ms 5756 KB Output is correct
28 Partially correct 62 ms 6012 KB Partially correct - number of queries: 8159
29 Partially correct 64 ms 6004 KB Partially correct - number of queries: 6735
30 Partially correct 58 ms 5988 KB Partially correct - number of queries: 8239
31 Partially correct 64 ms 6008 KB Partially correct - number of queries: 8268
32 Correct 14 ms 5760 KB Output is correct
33 Correct 7 ms 5028 KB Output is correct
34 Partially correct 74 ms 6008 KB Partially correct - number of queries: 8324
35 Correct 15 ms 5800 KB Output is correct
36 Partially correct 65 ms 6008 KB Partially correct - number of queries: 8272
37 Correct 14 ms 5928 KB Output is correct
38 Correct 14 ms 5752 KB Output is correct
39 Partially correct 70 ms 6008 KB Partially correct - number of queries: 8208
40 Partially correct 55 ms 5924 KB Partially correct - number of queries: 7084
41 Partially correct 71 ms 6008 KB Partially correct - number of queries: 8357
42 Partially correct 76 ms 6056 KB Partially correct - number of queries: 8357
43 Partially correct 64 ms 6056 KB Partially correct - number of queries: 8098
44 Partially correct 49 ms 6060 KB Partially correct - number of queries: 8336
45 Partially correct 73 ms 5976 KB Partially correct - number of queries: 8265
46 Partially correct 70 ms 6164 KB Partially correct - number of queries: 8347
47 Partially correct 47 ms 6064 KB Partially correct - number of queries: 8304
48 Partially correct 82 ms 6152 KB Partially correct - number of queries: 8350
49 Partially correct 37 ms 6056 KB Partially correct - number of queries: 8318
50 Partially correct 72 ms 6100 KB Partially correct - number of queries: 8358
51 Partially correct 70 ms 6056 KB Partially correct - number of queries: 8321
52 Partially correct 49 ms 5972 KB Partially correct - number of queries: 8353
53 Correct 12 ms 5752 KB Output is correct
54 Partially correct 71 ms 6048 KB Partially correct - number of queries: 8258
55 Partially correct 71 ms 6100 KB Partially correct - number of queries: 8361
56 Partially correct 78 ms 6164 KB Partially correct - number of queries: 8364
57 Partially correct 65 ms 6148 KB Partially correct - number of queries: 8249
58 Partially correct 41 ms 6052 KB Partially correct - number of queries: 8340
59 Partially correct 63 ms 6056 KB Partially correct - number of queries: 8357
60 Partially correct 61 ms 6008 KB Partially correct - number of queries: 8294
61 Correct 12 ms 5800 KB Output is correct
62 Correct 13 ms 5808 KB Output is correct
63 Correct 11 ms 5908 KB Output is correct
64 Correct 11 ms 5812 KB Output is correct
65 Correct 11 ms 5888 KB Output is correct
66 Correct 17 ms 5800 KB Output is correct
67 Correct 16 ms 5800 KB Output is correct
68 Correct 13 ms 5884 KB Output is correct
69 Correct 15 ms 5800 KB Output is correct
70 Correct 14 ms 5860 KB Output is correct
71 Partially correct 69 ms 6056 KB Partially correct - number of queries: 8376
72 Correct 15 ms 5888 KB Output is correct
73 Partially correct 67 ms 6036 KB Partially correct - number of queries: 8257
74 Partially correct 44 ms 6064 KB Partially correct - number of queries: 8305
75 Correct 12 ms 5760 KB Output is correct
76 Partially correct 66 ms 5928 KB Partially correct - number of queries: 7186
77 Partially correct 74 ms 6056 KB Partially correct - number of queries: 8340
78 Correct 14 ms 5760 KB Output is correct
79 Correct 39 ms 5880 KB Output is correct
80 Partially correct 60 ms 6008 KB Partially correct - number of queries: 8328
81 Partially correct 70 ms 6052 KB Partially correct - number of queries: 8308
82 Partially correct 65 ms 6160 KB Partially correct - number of queries: 8219
83 Correct 13 ms 5816 KB Output is correct
84 Partially correct 34 ms 6004 KB Partially correct - number of queries: 6865
85 Partially correct 37 ms 6140 KB Partially correct - number of queries: 8281
86 Correct 11 ms 5888 KB Output is correct
87 Correct 12 ms 5760 KB Output is correct
88 Correct 14 ms 5760 KB Output is correct
89 Correct 14 ms 5776 KB Output is correct
90 Correct 12 ms 5888 KB Output is correct
91 Correct 14 ms 5916 KB Output is correct
92 Correct 10 ms 5908 KB Output is correct
93 Correct 15 ms 5760 KB Output is correct
94 Correct 17 ms 5888 KB Output is correct
95 Correct 19 ms 5880 KB Output is correct
96 Correct 15 ms 5936 KB Output is correct
97 Correct 12 ms 5760 KB Output is correct