제출 #217148

#제출 시각아이디문제언어결과실행 시간메모리
217148maruiiBuilding 4 (JOI20_building4)C++14
100 / 100
320 ms41068 KiB
#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");
	}
	reverse(ans.begin(), ans.end());
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...