#include <iostream>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include "prize.h"
using namespace std;
int all[200005];
int l[200005],r[200005];
int ans=0;
int F(int L,int R,int here)
{
//printf("%d %d\n",L,R);
vector < int > t;
int x;
if(l[(L+R)/2]==-1)
{
ans++;
assert(ans<=10000);
t=ask((L+R)/2);
l[(L+R)/2]=t[0];
r[(L+R)/2]=t[1];
}
if(l[R]==-1)
{
ans++;
assert(ans<=10000);
t=ask(R);
l[R]=t[0];
r[R]=t[1];
}
if(l[L]==-1)
{
ans++;
assert(ans<=10000);
t=ask(L);
l[L]=t[0];
r[L]=t[1];
}
if(l[L]==0&&r[L]==0) return L;
if(l[R]==0&&r[R]==0) return R;
if(l[(L+R)/2]==0&&r[(L+R)/2]==0) return (L+R)/2;
if(L==R)
{
if(l[L]||r[L]) return -1;
return L;
}
else if(L+1==R)
{
if(l[L]||r[L])
{
if(l[R]||r[R]) return -1;
return R;
}
return L;
}
else
{
//printf("%d %d %d %d %d %d\n",l[L],r[L],l[(L+R)/2],r)
if(r[R]==r[(L+R)/2]) return F(L,(L+R)/2,here);
else if(l[L]==l[(L+R)/2]) return F((L+R)/2+1,R,here);
else if(here%2==0)
{
x=F((L+R)/2+1,R,1-here);
if(x!=-1) return x;
return F(L,(L+R)/2,1-here);
}
else
{
x=F(L,(L+R)/2+1,1-here);
if(x!=-1) return x;
return F((L+R)/2+1,R,1-here);
}
}
}
int find_best(int n)
{
vector < int > t;
int i,j,all=0;
for(i=0;i<n;i++) l[i]=r[i]=-1;
ans++;
assert(ans<=10000);
t=ask(0);
l[0]=t[0];
r[0]=t[1];
ans++;
assert(ans<=10000);
t=ask(n-1);
l[n-1]=t[0];
r[n-1]=t[1];
return F(0,n-1,0);
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:81:11: warning: unused variable 'j' [-Wunused-variable]
int i,j,all=0;
^
prize.cpp:81:13: warning: unused variable 'all' [-Wunused-variable]
int i,j,all=0;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1840 KB |
Output is correct |
2 |
Correct |
4 ms |
1784 KB |
Output is correct |
3 |
Correct |
4 ms |
1792 KB |
Output is correct |
4 |
Correct |
3 ms |
1936 KB |
Output is correct |
5 |
Correct |
3 ms |
1784 KB |
Output is correct |
6 |
Correct |
4 ms |
1944 KB |
Output is correct |
7 |
Correct |
4 ms |
1792 KB |
Output is correct |
8 |
Correct |
4 ms |
1920 KB |
Output is correct |
9 |
Correct |
3 ms |
1784 KB |
Output is correct |
10 |
Correct |
4 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
3 ms |
1948 KB |
Output is correct |
4 |
Correct |
4 ms |
1792 KB |
Output is correct |
5 |
Correct |
3 ms |
1912 KB |
Output is correct |
6 |
Correct |
5 ms |
1912 KB |
Output is correct |
7 |
Correct |
4 ms |
1912 KB |
Output is correct |
8 |
Correct |
3 ms |
1920 KB |
Output is correct |
9 |
Correct |
4 ms |
1784 KB |
Output is correct |
10 |
Correct |
4 ms |
1792 KB |
Output is correct |
11 |
Correct |
8 ms |
1784 KB |
Output is correct |
12 |
Correct |
8 ms |
1784 KB |
Output is correct |
13 |
Correct |
6 ms |
1792 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
32 ms |
1840 KB |
Output is correct |
16 |
Correct |
19 ms |
1784 KB |
Output is correct |
17 |
Correct |
18 ms |
2048 KB |
Output is correct |
18 |
Correct |
13 ms |
1912 KB |
Output is correct |
19 |
Correct |
38 ms |
1788 KB |
Output is correct |
20 |
Correct |
18 ms |
1280 KB |
Output is correct |
21 |
Partially correct |
25 ms |
1956 KB |
Partially correct - number of queries: 6640 |
22 |
Correct |
32 ms |
1912 KB |
Output is correct |
23 |
Correct |
5 ms |
1920 KB |
Output is correct |
24 |
Correct |
9 ms |
1792 KB |
Output is correct |
25 |
Correct |
6 ms |
1936 KB |
Output is correct |
26 |
Correct |
6 ms |
1916 KB |
Output is correct |
27 |
Correct |
6 ms |
1912 KB |
Output is correct |
28 |
Correct |
11 ms |
1956 KB |
Output is correct |
29 |
Correct |
21 ms |
1936 KB |
Output is correct |
30 |
Correct |
16 ms |
1936 KB |
Output is correct |
31 |
Correct |
45 ms |
1792 KB |
Output is correct |
32 |
Correct |
5 ms |
1912 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
34 |
Partially correct |
35 ms |
1936 KB |
Partially correct - number of queries: 6188 |
35 |
Correct |
5 ms |
1920 KB |
Output is correct |
36 |
Correct |
26 ms |
1912 KB |
Output is correct |
37 |
Correct |
4 ms |
1948 KB |
Output is correct |
38 |
Correct |
5 ms |
1792 KB |
Output is correct |
39 |
Partially correct |
46 ms |
1784 KB |
Partially correct - number of queries: 5809 |
40 |
Correct |
20 ms |
1812 KB |
Output is correct |
41 |
Correct |
15 ms |
1784 KB |
Output is correct |
42 |
Correct |
9 ms |
1940 KB |
Output is correct |
43 |
Correct |
8 ms |
2044 KB |
Output is correct |
44 |
Partially correct |
56 ms |
1784 KB |
Partially correct - number of queries: 5355 |
45 |
Partially correct |
41 ms |
1912 KB |
Partially correct - number of queries: 5503 |
46 |
Correct |
41 ms |
1852 KB |
Output is correct |
47 |
Correct |
42 ms |
1784 KB |
Output is correct |
48 |
Correct |
11 ms |
1784 KB |
Output is correct |
49 |
Correct |
37 ms |
2040 KB |
Output is correct |
50 |
Correct |
16 ms |
1920 KB |
Output is correct |
51 |
Partially correct |
51 ms |
1792 KB |
Partially correct - number of queries: 5362 |
52 |
Correct |
46 ms |
1912 KB |
Output is correct |
53 |
Correct |
5 ms |
1784 KB |
Output is correct |
54 |
Partially correct |
39 ms |
1852 KB |
Partially correct - number of queries: 5174 |
55 |
Correct |
26 ms |
1912 KB |
Output is correct |
56 |
Correct |
23 ms |
1784 KB |
Output is correct |
57 |
Correct |
6 ms |
1920 KB |
Output is correct |
58 |
Correct |
9 ms |
1852 KB |
Output is correct |
59 |
Correct |
14 ms |
1784 KB |
Output is correct |
60 |
Correct |
11 ms |
1912 KB |
Output is correct |
61 |
Correct |
3 ms |
1912 KB |
Output is correct |
62 |
Correct |
8 ms |
2048 KB |
Output is correct |
63 |
Correct |
4 ms |
1936 KB |
Output is correct |
64 |
Correct |
2 ms |
1852 KB |
Output is correct |
65 |
Correct |
5 ms |
1784 KB |
Output is correct |
66 |
Correct |
4 ms |
1832 KB |
Output is correct |
67 |
Correct |
4 ms |
1856 KB |
Output is correct |
68 |
Correct |
4 ms |
1792 KB |
Output is correct |
69 |
Correct |
4 ms |
1784 KB |
Output is correct |
70 |
Correct |
5 ms |
1784 KB |
Output is correct |
71 |
Partially correct |
62 ms |
1920 KB |
Partially correct - number of queries: 7216 |
72 |
Correct |
9 ms |
1792 KB |
Output is correct |
73 |
Partially correct |
39 ms |
1944 KB |
Partially correct - number of queries: 7118 |
74 |
Partially correct |
48 ms |
1920 KB |
Partially correct - number of queries: 7160 |
75 |
Correct |
6 ms |
1792 KB |
Output is correct |
76 |
Partially correct |
45 ms |
1920 KB |
Partially correct - number of queries: 6218 |
77 |
Partially correct |
53 ms |
1792 KB |
Partially correct - number of queries: 7360 |
78 |
Correct |
11 ms |
1792 KB |
Output is correct |
79 |
Correct |
34 ms |
1792 KB |
Output is correct |
80 |
Partially correct |
47 ms |
1792 KB |
Partially correct - number of queries: 6457 |
81 |
Partially correct |
28 ms |
1956 KB |
Partially correct - number of queries: 7362 |
82 |
Partially correct |
35 ms |
1792 KB |
Partially correct - number of queries: 6447 |
83 |
Correct |
4 ms |
1920 KB |
Output is correct |
84 |
Partially correct |
38 ms |
2048 KB |
Partially correct - number of queries: 6169 |
85 |
Partially correct |
53 ms |
1792 KB |
Partially correct - number of queries: 7377 |
86 |
Correct |
7 ms |
1944 KB |
Output is correct |
87 |
Correct |
5 ms |
2048 KB |
Output is correct |
88 |
Correct |
9 ms |
1792 KB |
Output is correct |
89 |
Correct |
6 ms |
1920 KB |
Output is correct |
90 |
Correct |
5 ms |
1944 KB |
Output is correct |
91 |
Correct |
5 ms |
1892 KB |
Output is correct |
92 |
Correct |
3 ms |
1792 KB |
Output is correct |
93 |
Correct |
8 ms |
1792 KB |
Output is correct |
94 |
Correct |
7 ms |
1792 KB |
Output is correct |
95 |
Correct |
8 ms |
1920 KB |
Output is correct |
96 |
Correct |
8 ms |
1792 KB |
Output is correct |
97 |
Correct |
4 ms |
1792 KB |
Output is correct |