Submission #217147

#	Time	Username	Problem	Language	Result	Execution time	Memory
217147		maruii	Building 4 (JOI20_building4)	C++14	0 / 100	4 ms	384 KiB

building4

#include <bits/stdc++.h>
using namespace std;
int N, A[1000001][2], L[1000001][2], R[1000001][2];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N * 2; ++i) cin >> A[i][0];
	for (int i = 1; i <= N * 2; ++i) cin >> A[i][1];
	for (int i = 1; i <= N * 2; ++i) {
		L[i][0] = L[i][1] = 1e9;
		R[i][0] = R[i][1] = -1e9;
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				if (A[i - 1][j] <= A[i][k]) {
					L[i][k] = min(L[i][k], L[i - 1][j] + (k == 0));
					R[i][k] = max(R[i][k], R[i - 1][j] + (k == 0));
				}
			}
		}
	}
	string ans;
	int a = 0, pre = 1e9;
	for (int i = N * 2; i >= 1; --i) {
		if (pre >= A[i][0] && L[i][0] <= N - a && N - a <= R[i][0]) {
			pre = A[i][0];
			ans += 'A';
			++a;
			continue;
		}
		if (pre >= A[i][1] && L[i][1] <= N - a && N - a <= R[i][1]) {
			pre = A[i][1];
			ans += 'B';
			continue;
		}
		return !printf("-1");
	}
	cout << ans;
	return 0;
}

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