Submission #1240312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240312		antromancap	Building 4 (JOI20_building4)	C++20	100 / 100	147 ms	25868 KiB

building4

#include <bits/stdc++.h>

using namespace std;

template <class T> bool mini(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <class T> bool maxi(T &x, const T &y) { return y > x ? x = y, 1 : 0; }

const int N = 1e6 + 1;
int n, a[N][2], mn[N][2], mx[N][2];
char ans[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int j = 0; j < 2; j++)
		for (int i = 1; i <= 2 * n; i++) cin >> a[i][j];

	memset(mn, 0x3f, sizeof mn);
	mn[1][0] = mx[1][0] = 0;
	mn[1][1] = mx[1][1] = 1;
	for (int i = 2; i <= 2 * n; i++)
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				if (a[i][j] < a[i - 1][k]) continue;
				mini(mn[i][j], mn[i - 1][k] + j);
				maxi(mx[i][j], mx[i - 1][k] + j);
			}
		}

	for (int j = 0; j < 2; j++) {
		if (mn[2 * n][j] > n || mx[2 * n][j] < n) continue;
		int t = j, cnt = n, pre = 0;
		for (int i = 2 * n; i; i--) {
			if (i < 2 * n && a[i][t] > a[i + 1][pre]) t ^= 1;
			else if (mn[i][t] > cnt || mx[i][t] < cnt) t ^= 1;
			cnt -= t;
			pre = t;
			ans[i] = t ? 'B' : 'A';
		}
		for (int i = 1; i <= 2 * n; i++) cout << ans[i];
		exit(0);
	}
	cout << -1;
}

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