#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 500005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int n,r,w,ori[N],m,i,res,pos;
II a[N];
int label(int k)
{
return 1-(k<w)+(k>w);
}
struct pt { int pos,jump; };
pt cal(int x)
{
//Init
if(w>n+1) while(1) {};
int i;
for(i=1;i<x;i++) a[i]={ (i-1)/2,label(ori[i]) };
a[x]={ (x-1)/2,label(w) };
for(i=x;i<=2*n-1;i++) a[i+1]={ i/2,label(ori[i]) };
m=2*n;
int cur1=a[1].snd,cur2=a[2].snd,cnt[3],j=3,jump=0;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=3*n;i++)
{
//Find the winner and loser in target 1
if(cur1>cur2) swap(cur1,cur2);
a[++m]={ i+n-1,cur2 };
cnt[cur2]++;
jump+=(cur2==1);
// Find next archer go to target 1
while(j<=m && a[j].fst<=i) cnt[a[j++].snd]++;
int to_1;
if(cnt[0]) to_1=0; else if(cnt[1]) to_1=1; else to_1=2;
cur2=to_1; cnt[to_1]--;
if(i>=2*n && (cur1==1) || (cur2==1))
{
int to_r=r-i,to_r_mod=(r-i+n)%n;
if(to_r_mod==0) to_r_mod=n;
if(i>=r) return { n-to_r_mod+1,jump };
return { n-to_r_mod+1,jump+1+(to_r-1)/n };
}
}
}
int main()
{
// freopen("archery.inp","r",stdin);
//freopen("archery.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>r>>w;
for(i=1;i<=2*n-1;i++) cin>>ori[i];
if(w==1) { cout<<1; return 0; }
// cal(1); return 0;
res=2*n+1;
for(i=0;i<=3;i++)
{
int l=1,r=2*n;
while(l<r)
{
int mid=(l+r)>>1;
pt x=cal(mid);
if(x.jump<=i) r=mid; else l=mid+1;
}
pt x=cal(l);
if(x.jump && res>x.pos)
{
res=x.pos;
pos=l;
}
}
cout<<pos;
}
Compilation message
archery.cpp: In function 'pt cal(int)':
archery.cpp:49:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
49 | if(i>=2*n && (cur1==1) || (cur2==1))
| ~~~~~~~^~~~~~~~~~~~
archery.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
57 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
5 ms |
9308 KB |
Execution killed with signal 11 |
| 5 |
Execution timed out |
2087 ms |
2396 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2048 ms |
2396 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
4700 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
3 ms |
4956 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
7 ms |
9224 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
33 ms |
22492 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
6 ms |
9348 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
7 ms |
9304 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
3 ms |
4952 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
7 ms |
9308 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
5 ms |
9308 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
27 ms |
21748 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
5 ms |
9308 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
10 ms |
13660 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
2 ms |
4816 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
3 ms |
4972 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
3 ms |
4956 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
5 ms |
9308 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
6 ms |
9436 KB |
Execution killed with signal 11 |
| 21 |
Runtime error |
7 ms |
9308 KB |
Execution killed with signal 11 |
| 22 |
Runtime error |
11 ms |
13912 KB |
Execution killed with signal 11 |
| 23 |
Runtime error |
32 ms |
22612 KB |
Execution killed with signal 11 |
| 24 |
Execution timed out |
2028 ms |
2648 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2012 ms |
2392 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2069 ms |
2396 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2045 ms |
2648 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2025 ms |
4440 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2036 ms |
2392 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2051 ms |
2396 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2037 ms |
2648 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2039 ms |
5468 KB |
Time limit exceeded |
| 33 |
Execution timed out |
2045 ms |
2548 KB |
Time limit exceeded |
| 34 |
Execution timed out |
2001 ms |
2392 KB |
Time limit exceeded |
| 35 |
Execution timed out |
2007 ms |
2392 KB |
Time limit exceeded |
| 36 |
Execution timed out |
2053 ms |
2396 KB |
Time limit exceeded |
| 37 |
Execution timed out |
2047 ms |
2652 KB |
Time limit exceeded |
| 38 |
Execution timed out |
2091 ms |
2648 KB |
Time limit exceeded |
| 39 |
Execution timed out |
2004 ms |
2392 KB |
Time limit exceeded |
| 40 |
Execution timed out |
2069 ms |
2396 KB |
Time limit exceeded |
| 41 |
Execution timed out |
2044 ms |
2396 KB |
Time limit exceeded |
| 42 |
Execution timed out |
2013 ms |
2396 KB |
Time limit exceeded |
| 43 |
Execution timed out |
2060 ms |
2396 KB |
Time limit exceeded |
| 44 |
Execution timed out |
2093 ms |
2392 KB |
Time limit exceeded |
| 45 |
Execution timed out |
2064 ms |
2652 KB |
Time limit exceeded |
| 46 |
Execution timed out |
2066 ms |
2652 KB |
Time limit exceeded |
| 47 |
Execution timed out |
2005 ms |
5968 KB |
Time limit exceeded |
