oj.uz

Submission #100720

# Submission time Handle Problem Language Result Execution time Memory
100720 2019-03-13T16:05:07 Z Bodo171 The Big Prize (IOI17_prize) C++14
90 / 100
 109 ms 6264 KB 
#include "prize.h"
#include <fstream>
#include <vector>
#include <iostream>
#include <cmath>
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]);
}
int cate_dr(int poz)
{
    return (cate(poz)-cate_st(poz));
}
void solve(int st,int dr)
{
    if(st>dr) return;
    if(cate(st)<mx)
    {
        spec[++nr]=st;
        solve(st+1,dr);
        return;
    }
    if(cate(dr)<mx)
    {
        spec[++nr]=dr;
        solve(st,dr-1);
        return;
    }
    int m=(st+dr)/2;
    if(cate(m)<mx)
    {
        spec[++nr]=m;
        solve(st,m-1);
        solve(m+1,dr);
    }
    else
    {
        if(cate_st(st)+cate_dr(m)!=mx) solve(st,m-1);
        if(cate_st(m)+cate_dr(dr)!=mx) solve(m+1,dr);
    }
}
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)
            {
                if(!cate(i)) return i;
            }

    }
    spec[mx+1]=n;
    solve(0,n-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:75:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1;i<=mx;i++)
     ^~~
prize.cpp:78: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 12 ms 5880 KB Output is correct
2 Correct 13 ms 5760 KB Output is correct
3 Correct 11 ms 5752 KB Output is correct
4 Correct 12 ms 5880 KB Output is correct
5 Correct 11 ms 5880 KB Output is correct
6 Correct 14 ms 5880 KB Output is correct
7 Correct 14 ms 5780 KB Output is correct
8 Correct 13 ms 5752 KB Output is correct
9 Correct 12 ms 5760 KB Output is correct
10 Correct 11 ms 5760 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5888 KB Output is correct
2 Correct 11 ms 5760 KB Output is correct
3 Correct 9 ms 5916 KB Output is correct
4 Correct 14 ms 5752 KB Output is correct
5 Correct 13 ms 5752 KB Output is correct
6 Correct 13 ms 5752 KB Output is correct
7 Correct 9 ms 5908 KB Output is correct
8 Correct 14 ms 6008 KB Output is correct
9 Correct 8 ms 5908 KB Output is correct
10 Correct 12 ms 5888 KB Output is correct
11 Correct 23 ms 5800 KB Output is correct
12 Correct 20 ms 5832 KB Output is correct
13 Correct 19 ms 5800 KB Output is correct
14 Correct 35 ms 5112 KB Output is correct
15 Partially correct 42 ms 6264 KB Partially correct - number of queries: 7951
16 Partially correct 59 ms 6064 KB Partially correct - number of queries: 8349
17 Correct 13 ms 5752 KB Output is correct
18 Partially correct 69 ms 5996 KB Partially correct - number of queries: 8329
19 Correct 10 ms 5908 KB Output is correct
20 Partially correct 43 ms 5576 KB Partially correct - number of queries: 5553
21 Partially correct 40 ms 6056 KB Partially correct - number of queries: 8365
22 Partially correct 47 ms 6004 KB Partially correct - number of queries: 6471
23 Correct 14 ms 5752 KB Output is correct
24 Correct 20 ms 5752 KB Output is correct
25 Partially correct 60 ms 6028 KB Partially correct - number of queries: 7581
26 Partially correct 43 ms 6036 KB Partially correct - number of queries: 7462
27 Correct 9 ms 5828 KB Output is correct
28 Partially correct 75 ms 6008 KB Partially correct - number of queries: 7360
29 Partially correct 60 ms 5880 KB Partially correct - number of queries: 6459
30 Partially correct 73 ms 6092 KB Partially correct - number of queries: 8245
31 Correct 12 ms 5752 KB Output is correct
32 Correct 17 ms 5756 KB Output is correct
33 Correct 8 ms 4992 KB Output is correct
34 Partially correct 61 ms 5988 KB Partially correct - number of queries: 8361
35 Correct 14 ms 5880 KB Output is correct
36 Partially correct 62 ms 6028 KB Partially correct - number of queries: 8246
37 Correct 17 ms 5800 KB Output is correct
38 Correct 15 ms 5752 KB Output is correct
39 Partially correct 65 ms 5980 KB Partially correct - number of queries: 8236
40 Partially correct 64 ms 5992 KB Partially correct - number of queries: 7310
41 Partially correct 50 ms 6136 KB Partially correct - number of queries: 8275
42 Partially correct 65 ms 6008 KB Partially correct - number of queries: 8275
43 Partially correct 66 ms 6008 KB Partially correct - number of queries: 8097
44 Partially correct 74 ms 6004 KB Partially correct - number of queries: 8366
45 Partially correct 71 ms 6008 KB Partially correct - number of queries: 7550
46 Correct 13 ms 5752 KB Output is correct
47 Partially correct 65 ms 5928 KB Partially correct - number of queries: 7631
48 Partially correct 66 ms 6056 KB Partially correct - number of queries: 8326
49 Partially correct 77 ms 6148 KB Partially correct - number of queries: 8250
50 Partially correct 109 ms 6004 KB Partially correct - number of queries: 8323
51 Partially correct 66 ms 5952 KB Partially correct - number of queries: 8220
52 Partially correct 67 ms 6008 KB Partially correct - number of queries: 8334
53 Correct 14 ms 5884 KB Output is correct
54 Partially correct 69 ms 6036 KB Partially correct - number of queries: 8243
55 Correct 12 ms 5772 KB Output is correct
56 Partially correct 57 ms 6132 KB Partially correct - number of queries: 8336
57 Partially correct 68 ms 6032 KB Partially correct - number of queries: 8280
58 Partially correct 77 ms 6160 KB Partially correct - number of queries: 8308
59 Partially correct 73 ms 6008 KB Partially correct - number of queries: 8300
60 Partially correct 69 ms 6008 KB Partially correct - number of queries: 8259
61 Correct 15 ms 5752 KB Output is correct
62 Correct 15 ms 5888 KB Output is correct
63 Correct 13 ms 5760 KB Output is correct
64 Correct 15 ms 5808 KB Output is correct
65 Correct 11 ms 5880 KB Output is correct
66 Correct 17 ms 5780 KB Output is correct
67 Correct 16 ms 5760 KB Output is correct
68 Correct 11 ms 5752 KB Output is correct
69 Correct 16 ms 5880 KB Output is correct
70 Correct 13 ms 5752 KB Output is correct
71 Partially correct 72 ms 6136 KB Partially correct - number of queries: 9072
72 Correct 20 ms 5888 KB Output is correct
73 Partially correct 75 ms 6008 KB Partially correct - number of queries: 8960
74 Partially correct 56 ms 6008 KB Partially correct - number of queries: 9008
75 Correct 14 ms 5888 KB Output is correct
76 Partially correct 74 ms 6008 KB Partially correct - number of queries: 7920
77 Partially correct 76 ms 6056 KB Partially correct - number of queries: 8551
78 Correct 13 ms 5808 KB Output is correct
79 Correct 39 ms 5928 KB Output is correct
80 Partially correct 64 ms 6000 KB Partially correct - number of queries: 8460
81 Partially correct 59 ms 6028 KB Partially correct - number of queries: 8548
82 Partially correct 68 ms 6008 KB Partially correct - number of queries: 8483
83 Correct 13 ms 5760 KB Output is correct
84 Partially correct 58 ms 6008 KB Partially correct - number of queries: 7142
85 Partially correct 67 ms 6008 KB Partially correct - number of queries: 8505
86 Correct 11 ms 5888 KB Output is correct
87 Correct 13 ms 5888 KB Output is correct
88 Correct 12 ms 5884 KB Output is correct
89 Correct 14 ms 5752 KB Output is correct
90 Correct 14 ms 5808 KB Output is correct
91 Correct 11 ms 5760 KB Output is correct
92 Correct 12 ms 5800 KB Output is correct
93 Correct 15 ms 5760 KB Output is correct
94 Correct 15 ms 5760 KB Output is correct
95 Correct 20 ms 5760 KB Output is correct
96 Correct 16 ms 5760 KB Output is correct
97 Correct 11 ms 5808 KB Output is correct