Submission #529717

#	Time	Username	Problem	Language	Result	Execution time	Memory
529717		AriaH	Building 4 (JOI20_building4)	C++17	100 / 100	212 ms	26000 KiB

building4

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, A[2][N];

int dp[2][N], pd[2][N];

int main()
{
	fast_io;
	cin >> n;
	for(int j = 0; j < 2; j ++)
	{
		for(int i = 1; i <= n * 2; i ++)
		{
			cin >> A[j][i];
		}
	}
	A[0][0] = A[1][0] = -1e9;
	for(int i = 0; i < N; i ++) for(int j = 0;j  < 2; j ++) dp[j][i] = 1e9, pd[j][i] = -1e9;
	dp[0][0] = dp[1][0] = 0;
	pd[0][0] = pd[1][0] = 0;
	for(int i = 0; i < n * 2; i ++)
	{
		for(int j = 0; j < 2; j ++)
		{
			for(int k = 0; k < 2; k ++)
			{
				if(A[j][i] <= A[k][i + 1])
				{
					dp[k][i + 1] = min(dp[k][i + 1], dp[j][i] + (k == 0));
					pd[k][i + 1] = max(pd[k][i + 1], pd[j][i] + (k == 0));
				}
			}
		}
	}
	/*for(int i = 1; i <= n << 1; i ++)
	{
		for(int j = 0; j < 2; j ++)
		{
			printf("i = %d j = %d dp = %d pd = %d\n", i, j, dp[j][i], pd[j][i]);
		}
	}
	*/
	int id, j;
	if(dp[0][n << 1] <= n && pd[0][n << 1] >= n)
	{
		id = n << 1, j = 0;
	}
	else if(dp[1][n << 1] <= n && pd[1][n << 1] >= n)
	{
		id = n << 1, j = 1;
	}
	else
	{
		cout << -1 << endl;
		return 0;
	}
	int cnt = 0;
	string ans;
	while(id > 0)
	{
		cnt += (j == 0);
		if(j == 0)
		{
			ans += "A";
		}
		else
		{
			ans += "B";
		}
		///printf("id = %d j = %d dp = %d pd = %d\n", id, j, dp[j][id], pd[j][id]);
		int j2 = -1;
		for(int k = 0; k < 2; k ++)
		{
			if(A[k][id - 1] <= A[j][id] && dp[k][id - 1] <= n - cnt && pd[k][id - 1] >= n - cnt)
			{
				j2 = k;
			}
		}
		if(j2 == -1)
		{
			assert(0);
			///printf("id = %d j = %d ans = %s\n", id, j, ans.c_str());
			return cout << -10, 0;
		}
		j = j2;
		id --;
	}
	reverse(all(ans));
	cout << ans;
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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