#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 cuctrai,cucphai,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)
{
l=max(l,cuctrai);
r=min(r,cucphai);
if(l>r)
return;
int mid=(l+r)/2,v=mid,u=mid-1;
while(1)
{
l=max(l,cuctrai);
r=min(r,cucphai);
if(l>r)
return;
vector<int>s;
if(u>=l)
{
s=myAsk(u);
if(s[0]+s[1]!=lolipop)
{
lis.pb({u,s[0]+s[1]});
if(s[0]==0)
{
cuctrai=v+1;
u=l-1;
}
if(s[1]==0)
{
cucphai=v-1;
v=r+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]});
if(s[0]==0)
{
cuctrai=v+1;
u=l-1;
}
if(s[1]==0)
{
cucphai=v-1;
v=r+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;
cuctrai=0;
cucphai=n-1;
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:196:1: warning: control reaches end of non-void function [-Wreturn-type]
196 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1068 KB |
Output is correct |
2 |
Correct |
5 ms |
1068 KB |
Output is correct |
3 |
Correct |
6 ms |
1068 KB |
Output is correct |
4 |
Correct |
7 ms |
1104 KB |
Output is correct |
5 |
Correct |
5 ms |
1068 KB |
Output is correct |
6 |
Correct |
6 ms |
1084 KB |
Output is correct |
7 |
Correct |
6 ms |
1096 KB |
Output is correct |
8 |
Correct |
6 ms |
1076 KB |
Output is correct |
9 |
Correct |
6 ms |
1064 KB |
Output is correct |
10 |
Correct |
5 ms |
1104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1084 KB |
Output is correct |
2 |
Correct |
6 ms |
1096 KB |
Output is correct |
3 |
Correct |
6 ms |
1056 KB |
Output is correct |
4 |
Correct |
6 ms |
1080 KB |
Output is correct |
5 |
Correct |
6 ms |
1084 KB |
Output is correct |
6 |
Correct |
5 ms |
1084 KB |
Output is correct |
7 |
Correct |
6 ms |
1104 KB |
Output is correct |
8 |
Correct |
4 ms |
1060 KB |
Output is correct |
9 |
Correct |
3 ms |
1100 KB |
Output is correct |
10 |
Correct |
5 ms |
1104 KB |
Output is correct |
11 |
Correct |
9 ms |
1224 KB |
Output is correct |
12 |
Correct |
5 ms |
1064 KB |
Output is correct |
13 |
Correct |
11 ms |
1568 KB |
Output is correct |
14 |
Correct |
4 ms |
1104 KB |
Output is correct |
15 |
Correct |
6 ms |
1300 KB |
Output is correct |
16 |
Correct |
48 ms |
2408 KB |
Output is correct |
17 |
Correct |
3 ms |
1092 KB |
Output is correct |
18 |
Partially correct |
45 ms |
2516 KB |
Partially correct - number of queries: 5611 |
19 |
Correct |
5 ms |
1060 KB |
Output is correct |
20 |
Correct |
8 ms |
1388 KB |
Output is correct |
21 |
Correct |
10 ms |
1596 KB |
Output is correct |
22 |
Correct |
9 ms |
1224 KB |
Output is correct |
23 |
Correct |
6 ms |
1064 KB |
Output is correct |
24 |
Correct |
5 ms |
1048 KB |
Output is correct |
25 |
Correct |
32 ms |
1880 KB |
Output is correct |
26 |
Correct |
25 ms |
1880 KB |
Output is correct |
27 |
Correct |
4 ms |
1072 KB |
Output is correct |
28 |
Correct |
33 ms |
2504 KB |
Output is correct |
29 |
Correct |
33 ms |
2268 KB |
Output is correct |
30 |
Partially correct |
42 ms |
2536 KB |
Partially correct - number of queries: 5568 |
31 |
Correct |
3 ms |
1088 KB |
Output is correct |
32 |
Correct |
8 ms |
1452 KB |
Output is correct |
33 |
Correct |
1 ms |
976 KB |
Output is correct |
34 |
Correct |
16 ms |
1552 KB |
Output is correct |
35 |
Correct |
6 ms |
1224 KB |
Output is correct |
36 |
Correct |
13 ms |
1352 KB |
Output is correct |
37 |
Correct |
6 ms |
1188 KB |
Output is correct |
38 |
Correct |
5 ms |
1096 KB |
Output is correct |
39 |
Correct |
23 ms |
1724 KB |
Output is correct |
40 |
Correct |
44 ms |
2544 KB |
Output is correct |
41 |
Correct |
28 ms |
1868 KB |
Output is correct |
42 |
Correct |
14 ms |
1904 KB |
Output is correct |
43 |
Correct |
24 ms |
1908 KB |
Output is correct |
44 |
Correct |
21 ms |
1668 KB |
Output is correct |
45 |
Correct |
9 ms |
1532 KB |
Output is correct |
46 |
Correct |
7 ms |
1084 KB |
Output is correct |
47 |
Correct |
24 ms |
1608 KB |
Output is correct |
48 |
Correct |
39 ms |
2160 KB |
Output is correct |
49 |
Correct |
6 ms |
1196 KB |
Output is correct |
50 |
Partially correct |
28 ms |
2628 KB |
Partially correct - number of queries: 5593 |
51 |
Correct |
20 ms |
1636 KB |
Output is correct |
52 |
Correct |
5 ms |
1092 KB |
Output is correct |
53 |
Correct |
8 ms |
1192 KB |
Output is correct |
54 |
Correct |
19 ms |
1704 KB |
Output is correct |
55 |
Correct |
6 ms |
1096 KB |
Output is correct |
56 |
Partially correct |
49 ms |
2620 KB |
Partially correct - number of queries: 5655 |
57 |
Correct |
38 ms |
2072 KB |
Output is correct |
58 |
Correct |
18 ms |
2136 KB |
Output is correct |
59 |
Correct |
25 ms |
1920 KB |
Output is correct |
60 |
Correct |
14 ms |
1944 KB |
Output is correct |
61 |
Correct |
4 ms |
1224 KB |
Output is correct |
62 |
Correct |
7 ms |
1064 KB |
Output is correct |
63 |
Correct |
7 ms |
1224 KB |
Output is correct |
64 |
Correct |
6 ms |
1096 KB |
Output is correct |
65 |
Correct |
9 ms |
1056 KB |
Output is correct |
66 |
Correct |
4 ms |
1096 KB |
Output is correct |
67 |
Correct |
4 ms |
1092 KB |
Output is correct |
68 |
Correct |
3 ms |
1132 KB |
Output is correct |
69 |
Correct |
5 ms |
1132 KB |
Output is correct |
70 |
Correct |
6 ms |
1104 KB |
Output is correct |
71 |
Partially correct |
55 ms |
2632 KB |
Partially correct - number of queries: 6250 |
72 |
Correct |
10 ms |
1636 KB |
Output is correct |
73 |
Partially correct |
67 ms |
2608 KB |
Partially correct - number of queries: 6173 |
74 |
Partially correct |
61 ms |
2580 KB |
Partially correct - number of queries: 6206 |
75 |
Correct |
7 ms |
1216 KB |
Output is correct |
76 |
Partially correct |
45 ms |
2676 KB |
Partially correct - number of queries: 5458 |
77 |
Partially correct |
48 ms |
2556 KB |
Partially correct - number of queries: 6036 |
78 |
Correct |
9 ms |
1596 KB |
Output is correct |
79 |
Correct |
15 ms |
2496 KB |
Output is correct |
80 |
Partially correct |
65 ms |
2560 KB |
Partially correct - number of queries: 6049 |
81 |
Partially correct |
34 ms |
2560 KB |
Partially correct - number of queries: 6054 |
82 |
Partially correct |
61 ms |
2532 KB |
Partially correct - number of queries: 5983 |
83 |
Correct |
7 ms |
1232 KB |
Output is correct |
84 |
Partially correct |
50 ms |
2608 KB |
Partially correct - number of queries: 5016 |
85 |
Partially correct |
57 ms |
2632 KB |
Partially correct - number of queries: 6039 |
86 |
Correct |
8 ms |
1092 KB |
Output is correct |
87 |
Correct |
3 ms |
1092 KB |
Output is correct |
88 |
Correct |
5 ms |
1088 KB |
Output is correct |
89 |
Correct |
6 ms |
1104 KB |
Output is correct |
90 |
Correct |
7 ms |
1104 KB |
Output is correct |
91 |
Correct |
4 ms |
1104 KB |
Output is correct |
92 |
Correct |
7 ms |
1072 KB |
Output is correct |
93 |
Correct |
5 ms |
1364 KB |
Output is correct |
94 |
Correct |
9 ms |
1476 KB |
Output is correct |
95 |
Correct |
9 ms |
1476 KB |
Output is correct |
96 |
Correct |
9 ms |
1360 KB |
Output is correct |
97 |
Correct |
5 ms |
1088 KB |
Output is correct |