Submission #408636

#	Time	Username	Problem	Language	Result	Execution time	Memory
408636		Jasiekstrz	Archery (IOI09_archery)	C++17	100 / 100	45 ms	1940 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;
	deque<int> st;
	int cnt=0;

	// for i=1
	for(int j=2;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();
		}
	}
	for(int i=1;i<=n;i++)
	{
		// update
		if(i>1)
		{
			// pop
			if(tab[2*i-1]==-1 && tab[2*i-2]==-1)
			{
				if(!st.empty() && st.front()==i)
					st.pop_front();
				else
					cnt++;
			}
			else if(tab[2*i-1]==1 && tab[2*i-2]==1)
				cnt--;

			// push
			if(i==2)
			{
				if(tab[1]==1)
				{
					if(st.empty())
						cnt++;
					else
						st.pop_back();
				}
				if(tab[2]==1)
				{
					if(st.empty())
						cnt++;
					else
						st.pop_back();
				}
			}
			else
			{
				int j=i-1;
				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();
				}
			}
		}

		// changes only for current
		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;
		}

		// undoing changes only for current
		if(i==1)
			cnt--;
		if(tab[2*i-1]==1)
			cnt--;
		st.pop_back();
	}
	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 i=n
	deque<int> st;
	int cnt=0;
	one=true;
	if(tab[2*n-1]==-1)
	{
		if(fl==2*n-1)
		{
			one=false;
			if(n!=1)
				st.push_back(n);
		}
		if(n!=1)
			cnt++;
	}
	for(int j=n-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(n!=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 i=n;i>=1;i--)
	{
		// update
		if(i<n)
		{
			// pop
			if(tab[2*i+1]==-1)
			{
				if(fl==2*i+1)
				{
					one=true;
					if(!st.empty() && st.front()==i+1)
						st.pop_front();
					else
						cnt++;
				}
				cnt--;
			}
			if(i!=1)
			{
				if(tab[2*i-1]==1 && tab[2*i]==1)
				{
					if(!st.empty() && st.front()==i)
						st.pop_front();
					else
						cnt++;
				}
				else if(tab[2*i-1]==-1 && tab[2*i]==-1)
					cnt--;
				if(i==(fl+1)/2)
				{
					one=true;
					if(!st.empty() && st.front()==i)
						st.pop_front();
					else
						cnt++;
				}
			}
			if(i==1)
			{
				if((fl+1)/2==1)
					one=true;
				else if(tab[1]==-1 && tab[2]==-1)
				{
					cnt--;
				}
				if(tab[1]==1 || tab[2]==1)
				{
					if(!st.empty() && st.front()==1)
						st.pop_front();
					else
						cnt++;
				}
			}

			// push
			if(tab[2*i-1]==-1)
			{
				if(fl==2*i-1)
				{
					one=false;
					if(i!=1)
					{
						if(cnt==0)
							st.push_front(i);
						else
							cnt--;
					}
				}
				if(i!=1)
					cnt++;
			}
			if(tab[2*i+1]==1 && tab[2*i]==1)
				st.push_back(i+1);
			else if(tab[2*i+1]==-1 && tab[2*i]==-1)
			{
				if(st.empty())
					cnt++;
				else
					st.pop_back();
			}
		}

		// changes only for current
		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;
			if(cnt>((fl+2)/2-i+n)%n)
				w=st[st.size()-cnt];
		}
		else
			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;
		}

		// unoing changes only for current
		st.pop_back();
	}
	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:216:5: warning: 'fl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  216 |     if(fl==2*i-1)
      |     ^~

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