Submission #407194

#	Time	Username	Problem	Language	Result	Execution time	Memory
407194		Jasiekstrz	Archery (IOI09_archery)	C++17	18 / 100	61 ms	9284 KiB

archery

#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 (stderr)

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

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