#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,target[N],b[N];
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 };
jump+=(cur2==1);
// cerr<<cur1<<" "<<cur2<<'\n';
// 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 Final(int x)
{
int m=0,i;
for(i=1;i<x;i++) b[++m]=ori[i];
b[++m]=w;
for(i=x;i<=2*n-1;i++) b[++m]=ori[i];
for(i=1;i<=2*n;i++) target[b[i]]=(i-1)/2;
for(int step=1;step<=r;step++)
{
// for(i=1;i<=m;i++) cout<<b[i]<<" "<<target[b[i]]<<'\n';
// cout<<'\n';
if(b[1]<b[2]) target[b[2]]=n-1; else target[b[1]]=n-1;
for(i=3;i<=m;i+=2)
if(b[i]<b[i+1]) target[b[i]]--; else target[b[i+1]]--;
sort(b+1,b+m+1,[&](int i,int j){ return target[i]<target[j]; });
}
return target[w];
}
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];
// for(pos=1;pos<=2*n;pos++) cout<<(pos+1)/2<<" "<<Final(pos)+1<<'\n';
// cerr<<Final(100);
if(w==1) { cout<<n; return 0; }
// cerr<<cal(8).pos; return 0;
int l=cal(2*n).jump,r=cal(1).jump;
res=2*n+1;
for(i=l;i<=r;i++)
{
int l=1,r=2*n;
while(l<r)
{
int mid=(l+r+1)>>1;
pt x=cal(mid);
if(x.jump>=i) l=mid; else r=mid-1;
}
pt x=cal(l);
if(x.jump==i && (res>x.pos || (res==x.pos && pos<l)))
{
res=x.pos;
pos=l;
}
}
cout<<(pos+1)/2;
}
Compilation message
archery.cpp: In function 'pt cal(int)':
archery.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
56 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 5 |
Execution timed out |
2088 ms |
2396 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2040 ms |
2396 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 4 |
Incorrect |
12 ms |
4700 KB |
Output isn't correct |
| 5 |
Correct |
120 ms |
13516 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
4700 KB |
Output isn't correct |
| 9 |
Correct |
14 ms |
4564 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 11 |
Incorrect |
16 ms |
4700 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 13 |
Incorrect |
92 ms |
13148 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
4952 KB |
Output isn't correct |
| 15 |
Incorrect |
22 ms |
6744 KB |
Output isn't correct |
| 16 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 17 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 19 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 20 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 21 |
Incorrect |
15 ms |
4744 KB |
Output isn't correct |
| 22 |
Correct |
18 ms |
4700 KB |
Output is correct |
| 23 |
Runtime error |
45 ms |
28244 KB |
Execution killed with signal 11 |
| 24 |
Execution timed out |
2044 ms |
2396 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2056 ms |
2396 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2037 ms |
2396 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2015 ms |
2392 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2035 ms |
2652 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2067 ms |
2396 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2041 ms |
2392 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2073 ms |
2396 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2045 ms |
2908 KB |
Time limit exceeded |
| 33 |
Execution timed out |
2061 ms |
2396 KB |
Time limit exceeded |
| 34 |
Execution timed out |
2033 ms |
2396 KB |
Time limit exceeded |
| 35 |
Execution timed out |
2032 ms |
2396 KB |
Time limit exceeded |
| 36 |
Execution timed out |
2033 ms |
2392 KB |
Time limit exceeded |
| 37 |
Execution timed out |
2068 ms |
2396 KB |
Time limit exceeded |
| 38 |
Execution timed out |
2064 ms |
2396 KB |
Time limit exceeded |
| 39 |
Execution timed out |
2064 ms |
2396 KB |
Time limit exceeded |
| 40 |
Execution timed out |
2069 ms |
2396 KB |
Time limit exceeded |
| 41 |
Execution timed out |
2032 ms |
2392 KB |
Time limit exceeded |
| 42 |
Execution timed out |
2039 ms |
2396 KB |
Time limit exceeded |
| 43 |
Execution timed out |
2056 ms |
2396 KB |
Time limit exceeded |
| 44 |
Execution timed out |
2061 ms |
2396 KB |
Time limit exceeded |
| 45 |
Execution timed out |
2074 ms |
2396 KB |
Time limit exceeded |
| 46 |
Execution timed out |
2036 ms |
2396 KB |
Time limit exceeded |
| 47 |
Execution timed out |
2033 ms |
3152 KB |
Time limit exceeded |
