Submission #1300358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300358		nguyenletrung	Building 4 (JOI20_building4)	C++20	11 / 100	2092 ms	1864 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[1000005],b[1000005],c[1000005];

string ans,res;

//vector<int> free;

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+' ';
		res=res+' ';
	}
	
	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+1);
			gorig(i+1);
		}
	}
	
//	cout<<'?'<<ans<<endl;
//	for(int i=1;i<=n;i++)
//	{
//		if()
//	}
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(ans[i]=='A') cnt++;
		else
		if(ans[i]=='B') cnt--;
//		else
		if(ans[i]==' ')
		{
			if(a[i]<b[i]) 
			{
				res[i]='B';
				cnt--;
			}
			else
			if(b[i]<a[i]) 
			{
				res[i]='A';
				cnt++;
			}
			else 
			{
//				res[i]=' ';
//				cout<<i<<endl;
				cnt--;
			}
		}
	}
	
//	cout<<'?'<<res<<endl;
	
	for(int i=1;i<=n;i++)
	{
//		cout<<i<<endl;
		if(ans[i]==' '&&res[i]!=' ')
		{
			int mx=0,mn=0,sum=0,nexi=i;
			for(int j=i;j<=n;j++)
			{
//				if(j!=1&&max(a[j-1],b[j-1])<=min(a[j],b[j])) break;
				
				if(res[j]==' ') break;
				
				if(res[j]=='A') sum-=2;
				else sum+=2;
				
				mx=max(mx,sum);
				mn=min(mn,sum);
				nexi=j;
				
				if(j!=n&&max(a[j],b[j])<=min(a[j+1],b[j+1])) break;
			}
			
			if(cnt<0)
			{
				if(cnt+mx>0)
				{
					mx=0-cnt;
					cnt=0;
				}
				else cnt+=mx;
				
				int sum=0;
				bool ok=false;
				for(int j=i;j<=nexi;j++)
				{
					if(sum==mx) ok=true;
					
					if(!ok) 
					{
						if(res[j]=='A') ans[j]='B';
						else ans[j]='A';
					}
					else ans[j]=res[j];
					
					if(res[j]=='A') sum-=2;
					else sum+=2;
				}
			}
			else
			{
				if(cnt+mn<0)
				{
					mn=0-cnt;
					cnt=0;
				}
				else cnt+=mn;
				
				int sum=0;
				bool ok=false;
				for(int j=i;j<=nexi;j++)
				{
					if(sum==mn) ok=true;
					
					if(!ok)
					{
						if(res[j]=='A') ans[j]='B';
						else ans[j]='A';
					}
					else ans[j]=res[j];
					
					if(res[j]=='A') sum-=2;
					else sum+=2;
				}
			}
			
			i=nexi;
			
		}
	}
	
	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<<-1;
	else
	cout<<ans;
	
	
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

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