oj.uz

답안 #407194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407194 2021-05-18T15:37:00 Z Jasiekstrz Archery (IOI09_archery) C++17
18 / 100
 61 ms 9284 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Incorrect 3 ms 3404 KB Output isn't correct
4 Incorrect 3 ms 3532 KB Output isn't correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 3 ms 3404 KB Output is correct

Subtask #2
14.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Incorrect 3 ms 3404 KB Output isn't correct
4 Incorrect 7 ms 3836 KB Output isn't correct
5 Incorrect 61 ms 8328 KB Output isn't correct
6 Incorrect 3 ms 3404 KB Output isn't correct
7 Correct 3 ms 3456 KB Output is correct
8 Correct 7 ms 3916 KB Output is correct
9 Incorrect 9 ms 4220 KB Output isn't correct
10 Incorrect 3 ms 3404 KB Output isn't correct
11 Incorrect 10 ms 4044 KB Output isn't correct
12 Incorrect 3 ms 3532 KB Output isn't correct
13 Incorrect 42 ms 7620 KB Output isn't correct
14 Incorrect 4 ms 3532 KB Output isn't correct
15 Incorrect 12 ms 4488 KB Output isn't correct
16 Incorrect 3 ms 3404 KB Output isn't correct
17 Incorrect 3 ms 3404 KB Output isn't correct
18 Incorrect 3 ms 3532 KB Output isn't correct
19 Incorrect 4 ms 3532 KB Output isn't correct
20 Incorrect 4 ms 3532 KB Output isn't correct
21 Incorrect 9 ms 4216 KB Output isn't correct
22 Incorrect 12 ms 4344 KB Output isn't correct
23 Incorrect 61 ms 9284 KB Output isn't correct
24 Incorrect 3 ms 3404 KB Output isn't correct
25 Incorrect 3 ms 3404 KB Output isn't correct
26 Incorrect 4 ms 3552 KB Output isn't correct
27 Incorrect 9 ms 3916 KB Output isn't correct
28 Incorrect 38 ms 6540 KB Output isn't correct
29 Correct 3 ms 3404 KB Output is correct
30 Correct 4 ms 3532 KB Output is correct
31 Incorrect 7 ms 3956 KB Output isn't correct
32 Incorrect 47 ms 8184 KB Output isn't correct
33 Incorrect 2 ms 3404 KB Output isn't correct
34 Correct 3 ms 3404 KB Output is correct
35 Incorrect 3 ms 3404 KB Output isn't correct
36 Incorrect 3 ms 3468 KB Output isn't correct
37 Incorrect 7 ms 3848 KB Output isn't correct
38 Incorrect 9 ms 4108 KB Output isn't correct
39 Incorrect 3 ms 3404 KB Output isn't correct
40 Incorrect 3 ms 3404 KB Output isn't correct
41 Incorrect 3 ms 3468 KB Output isn't correct
42 Incorrect 3 ms 3452 KB Output isn't correct
43 Incorrect 4 ms 3592 KB Output isn't correct
44 Incorrect 5 ms 3624 KB Output isn't correct
45 Incorrect 8 ms 3916 KB Output isn't correct
46 Incorrect 8 ms 4044 KB Output isn't correct
47 Incorrect 54 ms 8864 KB Output isn't correct