oj.uz

Submission #100710

# Submission time Handle Problem Language Result Execution time Memory
100710 2019-03-13T15:05:59 Z Bodo171 The Big Prize (IOI17_prize) C++14
20 / 100
 85 ms 6156 KB 
#include "prize.h"
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
const int prdf=2;//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 9 ms 5780 KB Output is correct
2 Correct 8 ms 5760 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 7 ms 5752 KB Output is correct
5 Correct 9 ms 5820 KB Output is correct
6 Correct 7 ms 5856 KB Output is correct
7 Correct 8 ms 5784 KB Output is correct
8 Correct 9 ms 5752 KB Output is correct
9 Correct 7 ms 5764 KB Output is correct
10 Correct 6 ms 5760 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5788 KB Output is correct
2 Correct 9 ms 5752 KB Output is correct
3 Correct 8 ms 5752 KB Output is correct
4 Correct 9 ms 5672 KB Output is correct
5 Correct 8 ms 5864 KB Output is correct
6 Correct 7 ms 5800 KB Output is correct
7 Correct 8 ms 5856 KB Output is correct
8 Correct 8 ms 5860 KB Output is correct
9 Correct 7 ms 5776 KB Output is correct
10 Correct 8 ms 5760 KB Output is correct
11 Correct 11 ms 5800 KB Output is correct
12 Correct 9 ms 5916 KB Output is correct
13 Correct 13 ms 5752 KB Output is correct
14 Correct 13 ms 5108 KB Output is correct
15 Partially correct 50 ms 5940 KB Partially correct - number of queries: 7458
16 Partially correct 82 ms 6144 KB Partially correct - number of queries: 7876
17 Partially correct 70 ms 6008 KB Partially correct - number of queries: 7873
18 Partially correct 61 ms 6032 KB Partially correct - number of queries: 7877
19 Partially correct 36 ms 6012 KB Partially correct - number of queries: 7353
20 Partially correct 32 ms 5620 KB Partially correct - number of queries: 5050
21 Partially correct 66 ms 6008 KB Partially correct - number of queries: 7779
22 Partially correct 31 ms 6096 KB Partially correct - number of queries: 5783
23 Correct 8 ms 5880 KB Output is correct
24 Correct 10 ms 5772 KB Output is correct
25 Partially correct 61 ms 6072 KB Partially correct - number of queries: 7779
26 Partially correct 60 ms 6008 KB Partially correct - number of queries: 7769
27 Correct 9 ms 5800 KB Output is correct
28 Partially correct 60 ms 5928 KB Partially correct - number of queries: 7682
29 Partially correct 41 ms 6048 KB Partially correct - number of queries: 6254
30 Partially correct 40 ms 6148 KB Partially correct - number of queries: 7759
31 Partially correct 74 ms 6156 KB Partially correct - number of queries: 7788
32 Correct 9 ms 5812 KB Output is correct
33 Correct 7 ms 4992 KB Output is correct
34 Partially correct 66 ms 6060 KB Partially correct - number of queries: 7842
35 Correct 9 ms 5800 KB Output is correct
36 Partially correct 62 ms 6020 KB Partially correct - number of queries: 7792
37 Correct 14 ms 5752 KB Output is correct
38 Correct 8 ms 5792 KB Output is correct
39 Partially correct 63 ms 5928 KB Partially correct - number of queries: 7728
40 Partially correct 48 ms 5880 KB Partially correct - number of queries: 6603
41 Partially correct 62 ms 6136 KB Partially correct - number of queries: 7877
42 Partially correct 64 ms 6008 KB Partially correct - number of queries: 7877
43 Partially correct 56 ms 6008 KB Partially correct - number of queries: 7618
44 Partially correct 73 ms 6020 KB Partially correct - number of queries: 7856
45 Partially correct 51 ms 5924 KB Partially correct - number of queries: 7785
46 Partially correct 85 ms 6012 KB Partially correct - number of queries: 7867
47 Partially correct 70 ms 6000 KB Partially correct - number of queries: 7824
48 Partially correct 71 ms 6140 KB Partially correct - number of queries: 7870
49 Partially correct 65 ms 5976 KB Partially correct - number of queries: 7838
50 Partially correct 68 ms 6008 KB Partially correct - number of queries: 7878
51 Partially correct 32 ms 6036 KB Partially correct - number of queries: 7841
52 Partially correct 36 ms 6052 KB Partially correct - number of queries: 7872
53 Correct 8 ms 5884 KB Output is correct
54 Partially correct 72 ms 5980 KB Partially correct - number of queries: 7778
55 Partially correct 39 ms 6156 KB Partially correct - number of queries: 7881
56 Partially correct 33 ms 6036 KB Partially correct - number of queries: 7884
57 Partially correct 44 ms 6100 KB Partially correct - number of queries: 7769
58 Partially correct 37 ms 6144 KB Partially correct - number of queries: 7860
59 Partially correct 51 ms 6048 KB Partially correct - number of queries: 7877
60 Partially correct 73 ms 6040 KB Partially correct - number of queries: 7814
61 Correct 9 ms 5880 KB Output is correct
62 Correct 8 ms 5796 KB Output is correct
63 Correct 8 ms 5944 KB Output is correct
64 Correct 9 ms 5780 KB Output is correct
65 Incorrect 8 ms 5900 KB answer is not correct
66 Halted 0 ms 0 KB -