Submission #229649

#	Time	Username	Problem	Language	Result	Execution time	Memory
229649		dolphingarlic	Building 4 (JOI20_building4)	C++14	100 / 100	325 ms	30188 KiB

building4

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int a[1000001], b[1000001];
pair<int, int> dp[1000001][2];

void upd(pair<int, int> &X, pair<int, int> &Y) {
	X.first = min(X.first, Y.first);
	X.second = max(X.second, Y.second);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	FOR(i, 1, 2 * n + 1) cin >> a[i];
	FOR(i, 1, 2 * n + 1) cin >> b[i];
	dp[0][0] = dp[0][1] = {0, 0};
	FOR(i, 1, 2 * n + 1) {
		dp[i][0] = dp[i][1] = {n + 1, -n - 1};
		if (a[i] >= a[i - 1]) upd(dp[i][0], dp[i - 1][0]);
		if (a[i] >= b[i - 1]) upd(dp[i][0], dp[i - 1][1]);
		if (b[i] >= a[i - 1]) upd(dp[i][1], dp[i - 1][0]);
		if (b[i] >= b[i - 1]) upd(dp[i][1], dp[i - 1][1]);
		dp[i][1].first++, dp[i][1].second++;
	}

	string ans = "";
	for (int i = 2 * n, curr = INT_MAX; i; i--) {
		if (a[i] > curr || dp[i][0].first > n || dp[i][0].second < n) {
			if (b[i] > curr || dp[i][1].first > n || dp[i][1].second < n) return cout << -1, 0;
			ans += "B", curr = b[i], n--;
		} else ans += "A", curr = a[i];
	}
	
	reverse(ans.begin(), ans.end());
	cout << ans;
	return 0;
}

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