oj.uz

Submission #218660

# Submission time Handle Problem Language Result Execution time Memory
218660 2020-04-02T13:17:21 Z Andrei_Cotor Building 4 (JOI20_building4) C++11
0 / 100
 6 ms 512 KB 
//alt: la dinamica de n^2 se observa ca pozitiile cu 1 sunt consecutive
#include<iostream>
#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--;
	}
}

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);

	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(min(A[0][i-1],A[1][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(min(A[0][i-1],A[1][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;
		}
	}

	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Incorrect 6 ms 512 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Incorrect 6 ms 512 KB Output isn't correct
7 Halted 0 ms 0 KB -