Submission #1205583

#TimeUsernameProblemLanguageResultExecution timeMemory
1205583avighnaBuilding 4 (JOI20_building4)C11
0 / 100
0 ms324 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...