Submission #1300344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300344		nguyenletrung	Building 4 (JOI20_building4)	C++20	0 / 100	1 ms	340 KiB

building4

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
//#define int ll
using namespace std;
int n,a[500005],b[500005],c[500005];

string ans;

void golef(int id)
{
	if(id==1||max(a[id-1],b[id-1])<=c[id]) return;
	else
	{
		if(ans[id-1]!=' ')
		{
			if(c[id-1]>c[id])
			{
				cout<<-1;
				exit(0);
			}
			return;
		}
		
		if(a[id-1]<b[id-1])
		{
			c[id-1]=a[id-1];
			ans[id-1]='A';
		}
		else
		{
			c[id-1]=b[id-1];
			ans[id-1]='B';
		}
		
		golef(id-1);
	}
}

void gorig(int id)
{
	if(id==n||c[id]<=min(a[id+1],b[id+1])) return;
	else
	{
		if(ans[id+1]!=' ')
		{
			if(c[id]>c[id+1])
			{
				cout<<-1;
				exit(0);
			}
			return;
		}
		
		if(c[id]>max(a[id+1],b[id+1]))
		{
			cout<<-1;
			exit(0);
		}
		
		if(a[id+1]<b[id+1])
		{
			c[id+1]=b[id+1];
			ans[id+1]='B';
		}
		else
		{
			c[id+1]=a[id+1];
			ans[id+1]='A';
		}
		
		gorig(id+1);
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	n*=2;
	
	for(int i=0;i<=n+1;i++)
	{
		ans=ans+' ';
	}
	
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	
	for(int i=1;i<=n-1;i++)
	{
		if(ans[i]!=' ') continue;
		
		if(min(a[i],b[i])>max(a[i+1],b[i+1]))
		{
			cout<<-1;
			return 0;
		}
		
		if(max(a[i],b[i])>max(a[i+1],b[i+1]))
		{
			if(a[i]>b[i]) 
			{
				c[i]=b[i];
				ans[i]='B';	
			}
			else 
			{
				c[i]=a[i];
				ans[i]='A';
			}
			
			golef(i);
			gorig(i);
		}
			
		if(min(a[i],b[i])>min(a[i+1],b[i+1]))
		{
			if(a[i+1]>b[i+1])
			{
				c[i+1]=a[i+1];
				ans[i+1]='A';
			}
			else
			{
				c[i+1]=b[i+1];
				ans[i+1]='B';
			}
			
			golef(i);
			gorig(i);
		}
	}
	
//	cout<<'?'<<ans<<endl;
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(ans[i]=='A') cnt++;
		else cnt--;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(ans[i]==' ')
		{
			if(cnt<0)
			{
				cnt+=2;
				ans[i]='A';
			}
			else ans[i]='B';
		}
	}
	
	ans.erase(ans.begin(),ans.begin()+1);
	
	if(cnt==0) cout<<ans;
	else cout<<-1;
	
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

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