Submission #407367

#	Time	Username	Problem	Language	Result	Execution time	Memory
407367		Jasiekstrz	Archery (IOI09_archery)	C++17	45 / 100	2094 ms	5284 KiB

archery

#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;
	for(int i=1;i<2*n;i++)
	{
		if(tab[i]==1)
			continue;
		fl=(i+2)/2;
		break;
	}
	for(int i=fl;i<=n;i++)
	{
		vector<int> st;
		int cnt=0;
		for(int j=i-1;j>1;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();
			}
		}
		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();
			}
		}
		if(i!=1 && tab[2*i-1]==-1)
			cnt++;
		st.push_back(i);
		int w=st[st.size()-1-cnt];
		w=((i-(r-(w-i))-1)%n+n)%n+1;
		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 (stderr)

archery.cpp: In function 'int moving(int, int)':
archery.cpp:84:14: warning: 'fl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |   for(int j=i-1;j>1;j--)
      |             ~^~

• Subtask 1: 5 / 6
• Subtask 2: 40 / 94