#include <stdbool.h>
#include <stdio.h>
#define N 500001
int a[N << 1], b[N << 1];
int dp[N << 1][2][2];
char res[N << 1];
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= 2 * n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= 2 * n; ++i) {
scanf("%d", &b[i]);
}
for (int i = 1; i <= n << 1; ++i) {
int l0 = n, r0 = 0, l1 = n, r1 = 0;
if (a[i - 1] <= b[i]) {
l0 = min(l0, dp[i - 1][1][0]);
r0 = max(r0, dp[i - 1][1][1]);
}
if (b[i - 1] <= b[i]) {
l0 = min(l0, dp[i - 1][0][0]);
r0 = max(r0, dp[i - 1][0][1]);
}
if (a[i - 1] <= a[i]) {
l1 = min(l1, dp[i - 1][1][0] + 1);
r1 = max(r1, dp[i - 1][1][1] + 1);
}
if (b[i - 1] <= a[i]) {
l1 = min(l1, dp[i - 1][0][0] + 1);
r1 = max(r1, dp[i - 1][0][1] + 1);
}
dp[i][0][0] = l0, dp[i][0][1] = r0, dp[i][1][0] = l1, dp[i][1][1] = r1;
}
if (dp[n << 1][0][0] > n && n > dp[n << 1][0][1] && dp[n << 1][1][0] > n && n > dp[n << 1][1][1]) {
printf("-1\n");
return 0;
}
int *arr[] = {b, a};
for (int i = n << 1, j = n, k = dp[n << 1][1][0] <= n && n <= dp[n << 1][1][1]; i >= 1; --i) {
res[i] = 'B' - k;
if (dp[i - 1][1][0] <= j - k && j - k <= dp[i - 1][1][1] && a[i - 1] <= arr[k][i]) {
j -= k, k = 1;
} else {
j -= k, k = 0;
}
}
printf("%s\n", res + 1);
}
Compilation message (stderr)
building4.c: In function 'main':
building4.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
building4.c:17:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d", &a[i]);
| ^~~~~~~~~~~~~~~~~~
building4.c:20:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &b[i]);
| ^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |