Submission #218724

#	Time	Username	Problem	Language	Result	Execution time	Memory
218724		Andrei_Cotor	Building 4 (JOI20_building4)	C++11	100 / 100	448 ms	37240 KiB

building4

//alt: la dinamica de n^2 se observa ca pozitiile cu 1 sunt consecutive
#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;
}

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