Submission #240627

#	Time	Username	Problem	Language	Result	Execution time	Memory
240627		sven	Building 4 (JOI20_building4)	C++14	11 / 100	477 ms	273472 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2001;

int prec[MAXN * 2][MAXN][2];

int A[MAXN * 2];
int B[MAXN * 2];
int N;

void dp(int posActu , int score , int iEtage)
{
	//cout<<posActu<<" "<<score<<" "<<iEtage<<endl;
	if (posActu == 2 * N -1)
	{
		return;
	}
	if (iEtage == 0)
	{
		if (score < N && prec[posActu + 1][score + 1][0] == -1 && A[posActu] <= A[posActu + 1])
		{
		//	cout<<"QergqreGQ"<<endl;
			prec[posActu + 1][score + 1][0] = 1;
			dp(posActu + 1 , score + 1 , 0);
		}
		if (prec[posActu + 1][score][1] == -1 && A[posActu] <= B[posActu + 1])
		{
			prec[posActu + 1][score][1] = 2;
			dp(posActu + 1 , score , 1);
		}
	}
	else
	{
		if (score < N && prec[posActu + 1][score + 1][0] == -1 && B[posActu] <= A[posActu + 1])
		{
		//	cout<<"QeroogqreGQ"<<endl;

			prec[posActu + 1][score + 1][0] = 2;
			dp(posActu + 1 , score + 1 , 0);
		}
		if (prec[posActu + 1][score][1] == -1 && B[posActu] <= B[posActu + 1])
		{
			prec[posActu + 1][score][1] = 1;
			dp(posActu + 1 , score , 1);
		}
	}
}
int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0 ; i < N * 2 ; i++)
	{
		cin >> A[i];
	}
	for (int i = 0 ; i < N * 2 ; i++)
	{
		cin >> B[i];
	}
	for (int i = 0 ; i < MAXN * 2 ; i++)
	{
		for (int j = 0 ; j < MAXN ; j++)
		{
			prec[i][j][0] = prec[i][j][1] = -1;
		}
	}
	dp(0 , 1 , 0);
	dp(0 , 0 , 1);
	int posActu = 0;
	if (prec[2 * N - 1][N][0] != -1)
	{
		posActu = 0;
	}
	else if (prec[2* N - 1][N][1] != -1)
	{
		posActu = 1;
	}
	else
	{
		cout<<-1<<endl;
		exit(0);
	}
	vector <int> sol;
	int scoreActu = N;
	for (int i = 0 ; i < 2 * N ; i++)
	{
		//cout<<i<<" e"<<posActu<<" "<<scoreActu<<" "<<prec[2 * N -1 - i][scoreActu][posActu]<<" "<<2 * N - 1 - i<<endl;
		sol.push_back(posActu);
		if (i < 2 * N - 1)
		{
			int pp = posActu;
			if (prec[2 * N - 1 - i][scoreActu][posActu] == 2)
			{
			//	cout<<"a"<<endl;
				posActu = 1 - posActu;
			}
			scoreActu -= (pp == 0);

		}
	}
	for (int i = 2 * N -1 ; i >= 0 ; i--)
	{
		if (sol[i] == 0) cout<<"A";
		else cout<<"B";
	}
	cout<<endl;
	/*for (int k = 0 ; k < 2 ; k++)
	{
		for (int i = 0 ; i < 2 * N ; i++)
		{
			for (int j = 0 ; j <= N ; j++)
			{
				cout<<prec[i][j][k]<<" ";
			}
			cout<<endl;

		}
		cout<<endl;
	}*/

}

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