Submission #1205584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205584		avighna	Building 4 (JOI20_building4)	C11	0 / 100	0 ms	328 KiB

building4

#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);
    }
    if (r0 > n) {
      l0 = r0;
    }
    if (r1 > n) {
      l1 = r1;
    }
    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]);
      |     ^~~~~~~~~~~~~~~~~~

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