Submission #304562

#TimeUsernameProblemLanguageResultExecution timeMemory
304562EJOI2019AndrewBuilding 4 (JOI20_building4)C++14
100 / 100
304 ms37112 KiB
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stdlib.h>
 
using namespace std;
 
int A[2][1000005];
bool Mand[1000005];
int Rez[1000005];
int Chain[1000005];
 
void imposs()
{
	cout<<"-1\n";
	exit(0);
}
 
void markMandatory(int poz, int val)
{
	if(Mand[poz]==1 && Rez[poz]!=val)
		imposs();
	else if(Mand[poz])
		return;
 
	while(poz>=1)
	{
		Mand[poz]=1;
		Rez[poz]=val;
 
		if(Mand[poz-1])
		{
			if(A[Rez[poz-1]][poz-1]>A[val][poz])
				imposs();
			break;
		}
 
		int nr=0;
		int newval=-1;
		if(A[0][poz-1]<=A[val][poz])
		{
			nr++;
			newval=0;
		}
 
		if(A[1][poz-1]<=A[val][poz])
		{
			nr++;
			newval=1;
		}
 
		if(nr==2)
			break;
 
		if(newval==-1)
			imposs();
 
		val=newval;
		poz--;
	}
}
 
int getval(int poz)
{
	if(Mand[poz])
		return A[Rez[poz]][poz];
	return min(A[0][poz],A[1][poz]);
}
 
void flip(int st, int dr)
{
	for(int i=st; i<=dr; i++)
		Rez[i]=1-Rez[i];
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	//ifstream fi("data.in");
	int n;
	cin>>n;
 
	for(int i=1; i<=2*n; i++)
		cin>>A[0][i];
 
	for(int i=1; i<=2*n; i++)
		cin>>A[1][i];
 
	for(int i=1; i<=2*n; i++)
	{
		if(A[0][i]<=A[1][i])
		{
			if(getval(i-1)>A[0][i])
				markMandatory(i,1);
 
			if(i!=2*n && A[1][i]>max(A[0][i+1],A[1][i+1]))
				markMandatory(i,0);
		}
		else
		{ 
			if(getval(i-1)>A[1][i])
				markMandatory(i,0);
 
			if(i!=2*n && A[0][i]>max(A[0][i+1],A[1][i+1]))
				markMandatory(i,1);
		}
	}
 
	int nra=0;
	for(int i=1; i<=2*n; i++)
	{
		if(!Mand[i])
		{
			if(A[0][i]<=A[1][i])
				Rez[i]=0;
			else
				Rez[i]=1;
		}
 
		nra+=(Rez[i]==0);
	}
 
	bool sw=0;
	if(nra<n)
	{
		sw=1;
		for(int i=1; i<=2*n; i++)
		{
			swap(A[0][i],A[1][i]);
			Rez[i]=1-Rez[i];
		}
		nra=2*n-nra;
	}
 
	//convertesc unele A-uri in B, avand grija sa nu obtin conflicte
	for(int i=1; i<=2*n; i++)
	{
		if(Mand[i])
			continue;
 
		if(!Mand[i-1] && A[1-Rez[i-1]][i-1]>A[Rez[i]][i]) //cand ii dau flip lui i-1 trb sa-i dau si lui i
			Chain[i]=Chain[i-1];
		else
			Chain[i]=i;
	}
 
	int cnt=0;
	int dr=2*n;
	for(int i=2*n; i>=1; i--)
	{
		if(Mand[i])
			continue;
 
		if(Chain[i]!=Chain[i+1])
		{
			dr=i;
			cnt=0;
		}
 
		if(Rez[i]==0)
			cnt--;
		else
			cnt++;
 
		if(cnt<0 && nra+cnt>=n)
		{
			nra+=cnt;
			flip(i,dr);
			dr=i-1;
			cnt=0;
		}
	}
 
	if(nra>n)
		imposs();
 
	for(int i=1; i<=2*n; i++)
	{
		if(A[Rez[i-1]][i-1]>A[Rez[i]][i])
			imposs();
	}
 
	for(int i=1; i<=2*n; i++)
	{
		if(sw)
			Rez[i]=1-Rez[i];
 
		if(!Rez[i])
			cout<<"A";
		else
			cout<<"B";
	}
	cout<<"\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...