#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
int tab[2*N+10];
int stationary(int n)
{
int ans=n+1,g=n;
for(int i=1;i<=n;i++)
{
vector<int> st;
int cnt=0;
for(int j=i+1;j<=n;j++)
{
if(tab[2*j-1]==-1 && tab[2*j-2]==-1)
st.push_back(j);
else if(tab[2*j-1]==1 && tab[2*j-2]==1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
}
if(i!=1)
{
if(tab[1]==1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
if(tab[2]==1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
}
for(int j=2;j<i;j++)
{
if(tab[2*j-1]==-1 && tab[2*j]==-1)
st.push_back(j);
else if(tab[2*j-1]==1 && tab[2*j]==1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
}
if(i==1)
cnt++;
if(tab[2*i-1]==1)
cnt++;
st.push_back(i);
int w=st[st.size()-1-cnt];
if(w<ans || (w==ans && i>g))
{
ans=w;
g=i;
}
}
return g;
}
int moving(int n,int r)
{
int ans=n+1,g=n;
int fl;
bool one=false;
for(int i=1;i<2*n;i++)
{
if(tab[i]==1)
continue;
fl=i;
break;
}
for(int i=1;i<=n;i++)
{
vector<int> st;
int cnt=0;
one=true;
if(tab[2*i-1]==-1)
{
if(fl==2*i-1)
{
one=false;
if(i!=1)
st.push_back(i);
}
if(i!=1)
cnt++;
}
for(int j=i-1;j>1;j--)
{
if(tab[2*j-1]==1 && tab[2*j]==1)
st.push_back(j);
else if(tab[2*j-1]==-1 && tab[2*j]==-1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
if(j==(fl+1)/2)
{
one=false;
st.push_back(j);
}
}
if(i!=1)
{
if((fl+1)/2==1)
one=false;
else if(tab[1]==-1 && tab[2]==-1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
if(tab[1]==1 || tab[2]==1)
st.push_back(1);
}
for(int j=n;j>i;j--)
{
if(tab[2*j-1]==1 && tab[2*j-2]==1)
st.push_back(j);
else if(tab[2*j-1]==-1 && tab[2*j-2]==-1)
{
if(st.empty())
cnt++;
else
st.pop_back();
}
}
st.push_back(i);
int w=i;
//cerr<<i<<" "<<w<<" "<<cnt<<"\n";
//for(auto v:st)
// cerr<<v<<" ";
//cerr<<"\n\n";
if(one)
{
w=(fl+2)/2;
cnt-=(fl-i+n)%n;
}
if(cnt>0)
w=st[st.size()-1-cnt];
w=((i-(r-(w-i))-1)%n+n)%n+1;
//cerr<<i<<" "<<w<<" "<<cnt<<"\n";
//for(auto v:st)
// cerr<<v<<" ";
//cerr<<"\n\n";
if(w<ans || (w==ans && i>g))
{
ans=w;
g=i;
}
}
return g;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,r,x;
cin>>n>>r>>x;
for(int i=1;i<2*n;i++)
{
cin>>tab[i];
if(tab[i]>x)
tab[i]=1;
else
tab[i]=-1;
}
if(x==1)
cout<<n<<"\n";
else if(2<=x && x<=n+1)
cout<<moving(n,r)<<"\n";
else
cout<<stationary(n)<<"\n";
return 0;
}
Compilation message
archery.cpp: In function 'int moving(int, int)':
archery.cpp:72:6: warning: 'fl' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | int fl;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Correct |
25 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
9 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1801 ms |
448 KB |
Output is correct |
| 5 |
Execution timed out |
2070 ms |
1732 KB |
Time limit exceeded |
| 6 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 7 |
Correct |
4 ms |
204 KB |
Output is correct |
| 8 |
Correct |
905 ms |
548 KB |
Output is correct |
| 9 |
Correct |
1729 ms |
524 KB |
Output is correct |
| 10 |
Correct |
8 ms |
332 KB |
Output is correct |
| 11 |
Execution timed out |
2051 ms |
488 KB |
Time limit exceeded |
| 12 |
Correct |
30 ms |
332 KB |
Output is correct |
| 13 |
Execution timed out |
2069 ms |
1800 KB |
Time limit exceeded |
| 14 |
Correct |
103 ms |
372 KB |
Output is correct |
| 15 |
Execution timed out |
2057 ms |
588 KB |
Time limit exceeded |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
8 ms |
332 KB |
Output is correct |
| 18 |
Correct |
17 ms |
336 KB |
Output is correct |
| 19 |
Correct |
50 ms |
332 KB |
Output is correct |
| 20 |
Correct |
91 ms |
372 KB |
Output is correct |
| 21 |
Correct |
1655 ms |
588 KB |
Output is correct |
| 22 |
Execution timed out |
2058 ms |
588 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2044 ms |
2492 KB |
Time limit exceeded |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
5 ms |
204 KB |
Output is correct |
| 26 |
Correct |
109 ms |
332 KB |
Output is correct |
| 27 |
Execution timed out |
2066 ms |
460 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2070 ms |
2148 KB |
Time limit exceeded |
| 29 |
Correct |
9 ms |
332 KB |
Output is correct |
| 30 |
Correct |
89 ms |
376 KB |
Output is correct |
| 31 |
Correct |
1361 ms |
488 KB |
Output is correct |
| 32 |
Execution timed out |
2088 ms |
2160 KB |
Time limit exceeded |
| 33 |
Correct |
1 ms |
204 KB |
Output is correct |
| 34 |
Correct |
1 ms |
204 KB |
Output is correct |
| 35 |
Correct |
18 ms |
344 KB |
Output is correct |
| 36 |
Correct |
24 ms |
332 KB |
Output is correct |
| 37 |
Correct |
974 ms |
460 KB |
Output is correct |
| 38 |
Execution timed out |
2100 ms |
460 KB |
Time limit exceeded |
| 39 |
Correct |
1 ms |
204 KB |
Output is correct |
| 40 |
Correct |
5 ms |
332 KB |
Output is correct |
| 41 |
Correct |
16 ms |
332 KB |
Output is correct |
| 42 |
Correct |
24 ms |
344 KB |
Output is correct |
| 43 |
Correct |
87 ms |
344 KB |
Output is correct |
| 44 |
Correct |
344 ms |
408 KB |
Output is correct |
| 45 |
Correct |
1348 ms |
652 KB |
Output is correct |
| 46 |
Correct |
1903 ms |
476 KB |
Output is correct |
| 47 |
Execution timed out |
2098 ms |
2424 KB |
Time limit exceeded |
