Submission #408599

#	Time	Username	Problem	Language	Result	Execution time	Memory
408599		Jasiekstrz	Archery (IOI09_archery)	C++17	75 / 100	2100 ms	2492 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;
	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 (stderr)

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;
      |      ^~

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