Submission #1032561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032561		juicy	Building 4 (JOI20_building4)	C++17	100 / 100	172 ms	45384 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

array<int, 2> operator + (const array<int, 2> &a, int x) {
	return {a[0] + x, a[1] + x};
}

array<int, 2> mrg(const array<int, 2> &lt, const array<int, 2> &rt) {
	return {min(lt[0], rt[0]), max(lt[1], rt[1])};
}

bool inside(const array<int, 2> &a, int i) {
	return a[0] <= i && i <= a[1];
}

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

	const int inf = 1e9;

	int N; cin >> N;
	vector<int> a(2 * N), b(2 * N);
	for (int &x : a) {
		cin >> x;
	}
	for (int &x : b) {
		cin >> x;
	}
	vector<array<array<int, 2>, 2>> dp(2 * N);
	for (int i = 1; i < 2 * N; ++i) {
		for (int j = 0; j < 2; ++j) {
			dp[i][j] = {inf, -inf};
		}
	}
	dp[0][0] = {0, 0};
	dp[0][1] = {1, 1};
	for (int i = 1; i < 2 * N; ++i) {
		if (a[i - 1] <= a[i]) {
			dp[i][0] = mrg(dp[i][0], dp[i - 1][0]);
		}
		if (b[i - 1] <= a[i]) {
			dp[i][0] = mrg(dp[i][0], dp[i - 1][1]);
		}
		if (a[i - 1] <= b[i]) {
			dp[i][1] = mrg(dp[i][1], dp[i - 1][0] + 1);
		}
		if (b[i - 1] <= b[i]) {
			dp[i][1] = mrg(dp[i][1], dp[i - 1][1] + 1);
		}
	}
	int taken = N, lst = inf;
	string res;
	for (int i = 2 * N - 1; i >= 0; --i) {
		if (inside(dp[i][0], taken) && a[i] <= lst) {
			res += 'A';
			lst = a[i];
		} else if (inside(dp[i][1], taken) && b[i] <= lst) {
			res += 'B';
			taken -= 1;
			lst = b[i];
		} else {
			cout << -1;
			exit(0);
		}
	}
	reverse(res.begin(), res.end());
	cout << res;
	return 0;
}

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