#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
struct F
{
int sum,mn;
F() : sum(0),mn(0) {};
int f(int x)
{
return sum+max(-mn,x);
}
};
int tab[2*N+10];
F pref[N+10];
F suf[N+10];
bool was_l[N+10];
int nxt_l[N+10];
vector<int> holes[2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,r,x;
cin>>n>>r;
cin>>x;
for(int i=1;i<2*n;i++)
cin>>tab[i];
if(x==1)
{
cout<<n<<"\n";
return 0;
}
for(int i=1;i<2*n;i++)
{
if(tab[i]<x)
tab[i]=-1;
else
tab[i]=1;
}
if(2<=x && x<=n+1)
{
// moving
int fl=n;
for(int i=1;i<n;i++)
{
if(tab[2*i-1]==-1 || tab[2*i]==-1)
{
fl=i;
break;
}
}
for(int i=n;i>1;i--)
{
nxt_l[i]=fl;
if(tab[2*i-1]==-1 || tab[2*i-2]==-1)
fl=i;
}
nxt_l[1]=fl;
for(int i=n;i>1;i--)
{
suf[i]=suf[i+1];
if(tab[2*i-1]==-1 && tab[2*i-2]==-1)
suf[i].sum++;
else if(tab[2*i-1]==1 && tab[2*i-2]==1)
suf[i].sum--;
suf[i].mn=min(suf[i].mn,suf[i].sum);
}
if(tab[1]==-1 || tab[2]==-1)
was_l[1]=true;
else
was_l[1]=false;
for(int i=2;i<n;i++)
{
was_l[i]=was_l[i-1];
if(tab[2*i-1]==-1 || tab[2*i]==-1)
was_l[i]=true;
pref[i]=pref[i-1];
if(tab[2*i-1]==-1 && tab[2*i]==-1)
pref[i].sum++;
else if(tab[2*i-1]==1 && tab[2*i]==1)
pref[i].sum--;
pref[i].mn=min(pref[i].mn,pref[i].sum);
}
for(int i=2;i<n;i++)
{
if(tab[2*i-1]==1 && tab[2*i]==1)
holes[0].push_back(i);
}
for(int i=n;i>1;i--)
{
if(tab[2*i-1]==1 && tab[2*i-2]==1)
holes[1].push_back(i);
}
int hi=holes[1].size()-1;
int ans=n+1,g=n;
for(int i=1;i<=n;i++)
{
while(hi>=0 && holes[1][hi]<=i)
hi--;
int pos;
if(!was_l[i-1] && tab[2*i-1]!=-1)
pos=nxt_l[i];
else if(pref[i-1].f(0)==0)
pos=i;
else if(hi+pref[i-1].f(0)-1<holes[1].size())
pos=holes[1][hi+pref[i-1].f(0)-1];
else
pos=holes[0][hi+pref[i-1].f(0)-1-holes[1].size()];
int nhi;
{
int bg=-1,en=holes[1].size()-1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(holes[1][mid]<=pos)
en=mid-1;
else
bg=mid;
}
nhi=bg;
}
int tmp=suf[i+1].f(0);
if(tab[2*i-1]==-1)
tmp++;
if(tmp==0)
pos=pos;
else if(nhi+tmp-1<holes[1].size())
pos=holes[1][nhi+tmp-1];
else
pos=holes[0][nhi+tmp-1-holes[1].size()];
tmp=((i-(r-(pos-i))-1)%n+n)%n+1;
if(tmp<ans || (tmp==ans && i>g))
{
ans=tmp;
g=i;
}
}
cout<<g<<"\n";
return 0;
}
// stationary
for(int i=n;i>1;i--)
{
suf[i]=suf[i+1];
if(tab[2*i-1]==1 && tab[2*i-2]==1)
suf[i].sum++;
else if(tab[2*i-1]==-1 && tab[2*i-2]==-1)
suf[i].sum--;
suf[i].mn=min(suf[i].mn,suf[i].sum);
}
if(tab[1]==1 && tab[2]==1)
pref[1].sum=2;
else if(tab[1]==1 || tab[2]==1)
pref[1].sum=1;
for(int i=2;i<n;i++)
{
pref[i]=pref[i-1];
if(tab[2*i-1]==1 && tab[2*i]==1)
pref[i].sum++;
else if(tab[2*i-1]==-1 && tab[2*i]==-1)
pref[i].sum--;
pref[i].mn=min(pref[i].mn,pref[i].sum);
}
for(int i=2;i<n;i++)
{
if(tab[2*i-1]==-1 && tab[2*i]==-1)
holes[0].push_back(i);
}
for(int i=n;i>1;i--)
{
if(tab[2*i-1]==-1 && tab[2*i-2]==-1)
holes[1].push_back(i);
}
int hi=-1;
int ans=n+1,g=n;
for(int i=1;i<=n;i++)
{
while(hi+1<holes[0].size() && holes[0][hi+1]<i)
hi++;
int tmp=pref[i-1].f(0);
tmp=suf[i+1].f(tmp);
if(tab[2*i-1]==1)
tmp++;
if(i==1)
tmp++;
if(tmp==0)
tmp=i;
else if(tmp<=hi+1)
tmp=holes[0][hi+1-tmp];
else
tmp=holes[1][holes[1].size()-tmp-hi-1];
if(tmp<ans || (tmp==ans && i>g))
{
ans=tmp;
g=i;
}
}
cout<<g<<"\n";
return 0;
}
Compilation message
archery.cpp: In function 'int main()':
archery.cpp:109:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | else if(hi+pref[i-1].f(0)-1<holes[1].size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
archery.cpp:135:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | else if(nhi+tmp-1<holes[1].size())
| ~~~~~~~~~^~~~~~~~~~~~~~~~
archery.cpp:188:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | while(hi+1<holes[0].size() && holes[0][hi+1]<i)
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
3532 KB |
Output isn't correct |
| 5 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
3836 KB |
Output isn't correct |
| 5 |
Incorrect |
61 ms |
8328 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 7 |
Correct |
3 ms |
3456 KB |
Output is correct |
| 8 |
Correct |
7 ms |
3916 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
4220 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 11 |
Incorrect |
10 ms |
4044 KB |
Output isn't correct |
| 12 |
Incorrect |
3 ms |
3532 KB |
Output isn't correct |
| 13 |
Incorrect |
42 ms |
7620 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
3532 KB |
Output isn't correct |
| 15 |
Incorrect |
12 ms |
4488 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
3532 KB |
Output isn't correct |
| 19 |
Incorrect |
4 ms |
3532 KB |
Output isn't correct |
| 20 |
Incorrect |
4 ms |
3532 KB |
Output isn't correct |
| 21 |
Incorrect |
9 ms |
4216 KB |
Output isn't correct |
| 22 |
Incorrect |
12 ms |
4344 KB |
Output isn't correct |
| 23 |
Incorrect |
61 ms |
9284 KB |
Output isn't correct |
| 24 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 25 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 26 |
Incorrect |
4 ms |
3552 KB |
Output isn't correct |
| 27 |
Incorrect |
9 ms |
3916 KB |
Output isn't correct |
| 28 |
Incorrect |
38 ms |
6540 KB |
Output isn't correct |
| 29 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 30 |
Correct |
4 ms |
3532 KB |
Output is correct |
| 31 |
Incorrect |
7 ms |
3956 KB |
Output isn't correct |
| 32 |
Incorrect |
47 ms |
8184 KB |
Output isn't correct |
| 33 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 34 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 35 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 36 |
Incorrect |
3 ms |
3468 KB |
Output isn't correct |
| 37 |
Incorrect |
7 ms |
3848 KB |
Output isn't correct |
| 38 |
Incorrect |
9 ms |
4108 KB |
Output isn't correct |
| 39 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 40 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 41 |
Incorrect |
3 ms |
3468 KB |
Output isn't correct |
| 42 |
Incorrect |
3 ms |
3452 KB |
Output isn't correct |
| 43 |
Incorrect |
4 ms |
3592 KB |
Output isn't correct |
| 44 |
Incorrect |
5 ms |
3624 KB |
Output isn't correct |
| 45 |
Incorrect |
8 ms |
3916 KB |
Output isn't correct |
| 46 |
Incorrect |
8 ms |
4044 KB |
Output isn't correct |
| 47 |
Incorrect |
54 ms |
8864 KB |
Output isn't correct |
