#include<bits/stdc++.h>
#ifndef SKY
#include "prize.h"
#endif // SKY
using namespace std;
#define N 200010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
int n,lolipop;
int ktr[N];
ii f[N];
#ifdef SKY
int p[N];
vector<int> ask(int i)
{
cout<<"ask "<<i<<endl;
vector<int>res(2,0);
for(int j=0;j<i;j++)
if(p[j]<p[i])
res[0]++;
for(int j=i+1;j<n;j++)
if(p[j]<p[i])
res[1]++;
// cout<<i<<endl;
// for(int j=0;j<n;j++)cout<<p[j]<<" ";cout<<endl;
// cout<<res[0]<<" "<<res[1]<<endl;
return res;
}
#endif // SKY
int query=0;
vector<int>myAsk(int i)
{
query++;
assert(query<=1e4);
if(ktr[i]!=-1)
return {f[i].fs,f[i].sc};
vector<int>res=ask(i);
ktr[i]=1;
f[i]={res[0],res[1]};
return res;
}
vector<ii>lis;
void solve(int l,int r,int left_child,int right_child)
{
if(l>r)
return;
int mid=(l+r)/2,v=mid,u=mid-1;
while(1)
{
vector<int>s;
if(u>=l)
{
s=myAsk(u);
if(s[0]+s[1]!=lolipop)
{
lis.pb({u,s[0]+s[1]});
u--;
}else
{
if(s[0]-left_child!=0)
{
solve(l,u-1,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(v,r,s[0],right_child);
}
return;
}
}
if(v<=r)
{
s=myAsk(v);
if(s[0]+s[1]!=lolipop)
{
lis.pb({v,s[0]+s[1]});
v++;
}else
{
if(s[0]-left_child!=0)
{
solve(l,u,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(v+1,r,s[0],right_child);
}
return;
}
}
if(u<l&&v>r)
return;
}
/* for(int i=mid;i<=r;i++)
{
vector<int>s=myAsk(i);
if(s[0]+s[1]!=lolipop)
{
lis.pb(i);
}else
{
if(s[0]-left_child!=0)
{
solve(l,mid-1,left_child,s[1]);
}
if(s[1]-right_child!=0)
{
solve(i+1,r,s[0],right_child);
}
return;
}
}
for(int i=mid-1;i>=l;i--)
{
vector<int>s=myAsk(i);
if(s[0]+s[1]!=lolipop)
{
lis.pb(i);
}else
{
if(s[0]-left_child!=0)
{
solve(l,i-1,left_child,s[1]);
}
}
}*/
}
int find_best(int cc)
{
memset(ktr,-1,sizeof(ktr));
n=cc;
lis.clear();
if(n<=500)
{
for(int i=0;i<n;i++)
{
vector<int>s=myAsk(i);
if(s[0]==0&&s[1]==0)
return i;
}
}
lolipop=0;
for(int i=0;i<sqrt(n)+100;i++)
{
vector<int>s=myAsk(i);
lolipop=max(lolipop,s[0]+s[1]);
}
solve(0,n-1,0,0);
for(auto i:lis)
{
if(i.sc==0)
return i.fs;
}
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i];
cout<<find_best(n);
cout<<endl<<query<<endl;
return 0;
}
#endif // SKY
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:167:1: warning: control reaches end of non-void function [-Wreturn-type]
167 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1064 KB |
Output is correct |
2 |
Correct |
4 ms |
1092 KB |
Output is correct |
3 |
Correct |
4 ms |
1060 KB |
Output is correct |
4 |
Correct |
6 ms |
1068 KB |
Output is correct |
5 |
Correct |
6 ms |
1088 KB |
Output is correct |
6 |
Correct |
5 ms |
1104 KB |
Output is correct |
7 |
Correct |
3 ms |
1096 KB |
Output is correct |
8 |
Correct |
4 ms |
1064 KB |
Output is correct |
9 |
Correct |
5 ms |
1084 KB |
Output is correct |
10 |
Correct |
6 ms |
1096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1064 KB |
Output is correct |
2 |
Correct |
5 ms |
1088 KB |
Output is correct |
3 |
Correct |
5 ms |
1068 KB |
Output is correct |
4 |
Correct |
4 ms |
1096 KB |
Output is correct |
5 |
Correct |
6 ms |
1104 KB |
Output is correct |
6 |
Correct |
3 ms |
1096 KB |
Output is correct |
7 |
Correct |
3 ms |
1096 KB |
Output is correct |
8 |
Correct |
3 ms |
1096 KB |
Output is correct |
9 |
Correct |
4 ms |
1092 KB |
Output is correct |
10 |
Correct |
6 ms |
1104 KB |
Output is correct |
11 |
Correct |
10 ms |
1568 KB |
Output is correct |
12 |
Correct |
12 ms |
1556 KB |
Output is correct |
13 |
Correct |
11 ms |
1616 KB |
Output is correct |
14 |
Correct |
13 ms |
1244 KB |
Output is correct |
15 |
Partially correct |
53 ms |
2560 KB |
Partially correct - number of queries: 5375 |
16 |
Partially correct |
52 ms |
2520 KB |
Partially correct - number of queries: 5635 |
17 |
Partially correct |
42 ms |
2632 KB |
Partially correct - number of queries: 5639 |
18 |
Partially correct |
39 ms |
2600 KB |
Partially correct - number of queries: 5617 |
19 |
Partially correct |
56 ms |
2528 KB |
Partially correct - number of queries: 5362 |
20 |
Correct |
30 ms |
1736 KB |
Output is correct |
21 |
Partially correct |
50 ms |
2588 KB |
Partially correct - number of queries: 5624 |
22 |
Correct |
51 ms |
2632 KB |
Output is correct |
23 |
Correct |
5 ms |
1228 KB |
Output is correct |
24 |
Correct |
11 ms |
1572 KB |
Output is correct |
25 |
Partially correct |
49 ms |
2464 KB |
Partially correct - number of queries: 5284 |
26 |
Partially correct |
45 ms |
2504 KB |
Partially correct - number of queries: 5245 |
27 |
Correct |
8 ms |
1208 KB |
Output is correct |
28 |
Partially correct |
42 ms |
2496 KB |
Partially correct - number of queries: 5157 |
29 |
Correct |
48 ms |
2464 KB |
Output is correct |
30 |
Partially correct |
44 ms |
2544 KB |
Partially correct - number of queries: 5612 |
31 |
Partially correct |
48 ms |
2600 KB |
Partially correct - number of queries: 5639 |
32 |
Correct |
15 ms |
1640 KB |
Output is correct |
33 |
Correct |
1 ms |
976 KB |
Output is correct |
34 |
Partially correct |
48 ms |
2632 KB |
Partially correct - number of queries: 5666 |
35 |
Correct |
8 ms |
1316 KB |
Output is correct |
36 |
Partially correct |
53 ms |
2600 KB |
Partially correct - number of queries: 5593 |
37 |
Correct |
10 ms |
1452 KB |
Output is correct |
38 |
Correct |
6 ms |
1224 KB |
Output is correct |
39 |
Partially correct |
47 ms |
2568 KB |
Partially correct - number of queries: 5604 |
40 |
Correct |
49 ms |
2604 KB |
Output is correct |
41 |
Partially correct |
38 ms |
2612 KB |
Partially correct - number of queries: 5670 |
42 |
Partially correct |
71 ms |
2620 KB |
Partially correct - number of queries: 5670 |
43 |
Partially correct |
60 ms |
2592 KB |
Partially correct - number of queries: 5511 |
44 |
Partially correct |
54 ms |
2580 KB |
Partially correct - number of queries: 5623 |
45 |
Partially correct |
51 ms |
2472 KB |
Partially correct - number of queries: 5228 |
46 |
Partially correct |
47 ms |
2576 KB |
Partially correct - number of queries: 5673 |
47 |
Partially correct |
40 ms |
2496 KB |
Partially correct - number of queries: 5274 |
48 |
Partially correct |
64 ms |
2616 KB |
Partially correct - number of queries: 5697 |
49 |
Partially correct |
46 ms |
2596 KB |
Partially correct - number of queries: 5653 |
50 |
Partially correct |
51 ms |
2632 KB |
Partially correct - number of queries: 5653 |
51 |
Partially correct |
33 ms |
2608 KB |
Partially correct - number of queries: 5633 |
52 |
Partially correct |
48 ms |
2596 KB |
Partially correct - number of queries: 5631 |
53 |
Correct |
6 ms |
1172 KB |
Output is correct |
54 |
Partially correct |
28 ms |
2512 KB |
Partially correct - number of queries: 5597 |
55 |
Partially correct |
41 ms |
2732 KB |
Partially correct - number of queries: 5662 |
56 |
Partially correct |
52 ms |
2580 KB |
Partially correct - number of queries: 5661 |
57 |
Partially correct |
43 ms |
2620 KB |
Partially correct - number of queries: 5629 |
58 |
Partially correct |
53 ms |
2532 KB |
Partially correct - number of queries: 5593 |
59 |
Partially correct |
58 ms |
2632 KB |
Partially correct - number of queries: 5657 |
60 |
Partially correct |
48 ms |
2584 KB |
Partially correct - number of queries: 5665 |
61 |
Correct |
7 ms |
1232 KB |
Output is correct |
62 |
Correct |
3 ms |
1204 KB |
Output is correct |
63 |
Correct |
6 ms |
1216 KB |
Output is correct |
64 |
Correct |
8 ms |
1188 KB |
Output is correct |
65 |
Correct |
6 ms |
1044 KB |
Output is correct |
66 |
Correct |
12 ms |
1056 KB |
Output is correct |
67 |
Correct |
7 ms |
1104 KB |
Output is correct |
68 |
Correct |
6 ms |
1064 KB |
Output is correct |
69 |
Correct |
12 ms |
1104 KB |
Output is correct |
70 |
Correct |
9 ms |
1064 KB |
Output is correct |
71 |
Partially correct |
48 ms |
2584 KB |
Partially correct - number of queries: 6250 |
72 |
Correct |
12 ms |
1608 KB |
Output is correct |
73 |
Partially correct |
45 ms |
2632 KB |
Partially correct - number of queries: 6173 |
74 |
Partially correct |
56 ms |
2576 KB |
Partially correct - number of queries: 6206 |
75 |
Correct |
8 ms |
1224 KB |
Output is correct |
76 |
Partially correct |
54 ms |
2608 KB |
Partially correct - number of queries: 5458 |
77 |
Partially correct |
51 ms |
2720 KB |
Partially correct - number of queries: 6031 |
78 |
Correct |
9 ms |
1600 KB |
Output is correct |
79 |
Correct |
24 ms |
2468 KB |
Output is correct |
80 |
Partially correct |
36 ms |
2604 KB |
Partially correct - number of queries: 6052 |
81 |
Partially correct |
46 ms |
2552 KB |
Partially correct - number of queries: 6073 |
82 |
Partially correct |
49 ms |
2628 KB |
Partially correct - number of queries: 5971 |
83 |
Correct |
8 ms |
1260 KB |
Output is correct |
84 |
Partially correct |
53 ms |
2524 KB |
Partially correct - number of queries: 5102 |
85 |
Partially correct |
63 ms |
2620 KB |
Partially correct - number of queries: 6039 |
86 |
Correct |
6 ms |
1088 KB |
Output is correct |
87 |
Correct |
7 ms |
1104 KB |
Output is correct |
88 |
Correct |
7 ms |
1092 KB |
Output is correct |
89 |
Correct |
5 ms |
1096 KB |
Output is correct |
90 |
Correct |
7 ms |
1212 KB |
Output is correct |
91 |
Correct |
6 ms |
1088 KB |
Output is correct |
92 |
Correct |
8 ms |
1104 KB |
Output is correct |
93 |
Correct |
9 ms |
1392 KB |
Output is correct |
94 |
Correct |
10 ms |
1480 KB |
Output is correct |
95 |
Correct |
9 ms |
1484 KB |
Output is correct |
96 |
Correct |
9 ms |
1360 KB |
Output is correct |
97 |
Correct |
6 ms |
1096 KB |
Output is correct |