Submission #1165472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165472		AmirAli_H1	Building 4 (JOI20_building4)	C++20	100 / 100	153 ms	33832 KiB

building4

// In the name of Allah

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

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

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 7;
const int oo = 1e9 + 4;

int n; pll A[maxn];
pii dp[maxn][2];
vector<char> res;

void solve() {
	cin >> n; n *= 2;
	for (int i = 0; i < n; i++) cin >> A[i].F;
	for (int i = 0; i < n; i++) cin >> A[i].S;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			dp[i][0] = Mp(0, 0); dp[i][1] = Mp(1, 1);
		}
		else {
			dp[i][0] = dp[i][1] = Mp(oo, -oo);
			if (A[i].F >= A[i - 1].F) {
				pii f = dp[i - 1][0];
				dp[i][0].F = min(dp[i][0].F, f.F);
				dp[i][0].S = max(dp[i][0].S, f.S);
			}
			if (A[i].F >= A[i - 1].S) {
				pii f = dp[i - 1][1];
				dp[i][0].F = min(dp[i][0].F, f.F);
				dp[i][0].S = max(dp[i][0].S, f.S);
			}
			if (A[i].S >= A[i - 1].F) {
				pii f = dp[i - 1][0];
				dp[i][1].F = min(dp[i][1].F, f.F + 1);
				dp[i][1].S = max(dp[i][1].S, f.S + 1);
			}
			if (A[i].S >= A[i - 1].S) {
				pii f = dp[i - 1][1];
				dp[i][1].F = min(dp[i][1].F, f.F + 1);
				dp[i][1].S = max(dp[i][1].S, f.S + 1);
			}
		}
	}

	int j = n - 1, R = -1, x = (n / 2);
	if (dp[n - 1][0].F <= x && dp[n - 1][0].S >= x) R = 0;
	else if (dp[n - 1][1].F <= x && dp[n - 1][1].S >= x) R = 1;
	else {
		cout << -1 << endl;
		return ;
	}

	while (true) {
		if (R == 0) res.pb('A');
		else {
			res.pb('B'); x--;
		}
		if (j == 0) break;
		int valx = (R == 0) ? A[j].F : A[j].S;
		if (A[j - 1].F <= valx && dp[j - 1][0].F <= x && dp[j - 1][0].S >= x) {
			j--; R = 0;
		}
		else {
			j--; R = 1;
		}
	}
	reverse(all(res));

	for (int i = 0; i < n; i++) cout << res[i];
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	return 0;
}

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