Submission #1126429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126429		TAhmed33	Building 4 (JOI20_building4)	C++20	100 / 100	243 ms	28844 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
typedef long double ld;
const int MAXN = 1e6 + 25;
int a[MAXN][2], n, ans[MAXN];
pair <int, int> f[MAXN][2];
void construct (int pos, int x, int c) {
	ans[pos] = c; x -= c == 0;
	if (pos == 1) {
		return;
	}
	if (a[pos][c] >= a[pos - 1][0] && f[pos - 1][0].first <= x && x <= f[pos - 1][0].second) {
		construct(pos - 1, x, 0);
	} else if (a[pos][c] >= a[pos - 1][1] && f[pos - 1][1].first <= x && x <= f[pos - 1][1].second) {
		construct(pos - 1, x, 1);
	} else {
		assert(0);
	}
}
void solve () {
	cin >> n;
	n *= 2;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0];
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i][1];
	}
	f[1][0] = {1, 1};
	f[1][1] = {0, 0};
	for (int i = 2; i <= n; i++) {
		f[i][0] = {-1, -1};
		for (int j = 0; j < 2; j++) {
			if (f[i - 1][j].first == -1) {
				continue;
			}
			if (a[i][0] >= a[i - 1][j]) {
				if (f[i][0].first == -1) {
					f[i][0] = f[i - 1][j];
					f[i][0].first++; f[i][0].second++;
				} else {
					f[i][0].first = min(f[i][0].first, 1 + f[i - 1][j].first);
					f[i][0].second = max(f[i][0].second, 1 + f[i - 1][j].second);
				}
			}
		}
		f[i][1] = {-1, -1};
		for (int j = 0; j < 2; j++) {
			if (f[i - 1][j].first == -1) {
				continue;
			}
			if (a[i][1] >= a[i - 1][j]) {
				if (f[i][1].first == -1) {
					f[i][1] = f[i - 1][j];
				} else {
					f[i][1].first = min(f[i][1].first, f[i - 1][j].first);
					f[i][1].second = max(f[i][1].second, f[i - 1][j].second);
				}
			}
		}
	}
	for (int j = 0; j < 2; j++)
		if (f[n][j].first <= n / 2 && n / 2 <= f[n][j].second) {
			construct(n, n / 2, j);
			char v[2] = {'A', 'B'};
			for (int i = 1; i <= n; i++) {
				cout << v[ans[i]];
			}
			cout << '\n';
			return;
		}

	cout << "-1\n";
}				
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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