oj.uz

Submission #408636

# Submission time Handle Problem Language Result Execution time Memory
408636 2021-05-19T11:38:51 Z Jasiekstrz Archery (IOI09_archery) C++17
100 / 100
 45 ms 1940 KB 
#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

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.0 / 6.0

# 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 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
94.0 / 94.0

# 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 1 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 42 ms 1684 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 4 ms 472 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 29 ms 1356 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 8 ms 520 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 5 ms 532 KB Output is correct
22 Correct 9 ms 580 KB Output is correct
23 Correct 45 ms 1860 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 6 ms 460 KB Output is correct
28 Correct 31 ms 1368 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 5 ms 460 KB Output is correct
32 Correct 40 ms 1860 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 4 ms 460 KB Output is correct
38 Correct 6 ms 460 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 2 ms 332 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 2 ms 332 KB Output is correct
44 Correct 3 ms 332 KB Output is correct
45 Correct 5 ms 460 KB Output is correct
46 Correct 5 ms 460 KB Output is correct
47 Correct 45 ms 1940 KB Output is correct