Submission #388673

#	Time	Username	Problem	Language	Result	Execution time	Memory
388673		ogibogi2004	Building 4 (JOI20_building4)	C++14	0 / 100	4 ms	460 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
int a[MAXN][2];
int n;
int dpmin[MAXN][2];
int dpmax[MAXN][2];
string ans="";
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)cin>>a[i][0];
	for(int i=1;i<=2*n;i++)cin>>a[i][1];
	dpmin[1][1]=1;
	dpmin[1][0]=0;
	dpmax[1][1]=1;
	dpmax[1][0]=0;
	for(int i=2;i<=2*n;i++)
	{
		dpmin[i][0]=MAXN;
		dpmin[i][1]=MAXN;
		if(a[i][0]>=a[i-1][0])
		{
			dpmin[i][0]=min(dpmin[i][0],dpmin[i-1][0]);
			dpmax[i][0]=max(dpmax[i][0],dpmax[i-1][0]);
		}
		if(a[i][0]>=a[i-1][1])
		{
			dpmin[i][0]=min(dpmin[i][1],dpmin[i-1][1]);
			dpmax[i][0]=max(dpmax[i][1],dpmax[i-1][1]);
		}
		if(a[i][1]>=a[i-1][0])
		{
			dpmin[i][1]=min(dpmin[i][0],dpmin[i-1][0]+1);
			dpmax[i][1]=max(dpmax[i][0],dpmax[i-1][0]+1);
		}
		if(a[i][1]>=a[i-1][1])
		{
			dpmin[i][1]=min(dpmin[i][1],dpmin[i-1][1]+1);
			dpmax[i][1]=max(dpmax[i][1],dpmax[i-1][1]+1);
		}
		//cout<<dpmax[i][1]<<" "<<dpmax[i][0]<<" "<<dpmin[i][1]<<" "<<dpmin[i][0]<<endl;
	}
	int t,cnt;
	if(dpmax[2*n][0]>=n&&dpmin[2*n][0]<=n)
	{
		ans+='A';
		t=0;
		cnt=0;
	}
	else if(dpmax[2*n][1]>=n&&dpmin[2*n][1]<=n)
	{
		ans+='B';
		t=1;
		cnt=1;
	}
	else
	{
		cout<<"-1\n";
		return 0;
	}
	for(int i=2*n-1;i>=1;i--)
	{
		if(a[i+1][t]>=a[i][0]&&dpmin[i][0]<=n-cnt&&dpmax[i][0]>=n-cnt)
		{
			t=0;
			ans+='A';
		}
		else
		{
			t=1;
			ans+='B';
			cnt++;
		}
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;
return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 89