Submission #211541

#	Time	Username	Problem	Language	Result	Execution time	Memory
211541		RezwanArefin01	Building 4 (JOI20_building4)	C++17	100 / 100	507 ms	119968 KiB

building4

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e6 + 5;

int n, a[2][N], dp[2][2][N], idx;
char s[N];

int f(int c, int x, int i) {
  if(i == 2 * n) return c == x;

  int &ret = dp[c][x][i]; 
  if(~ret) return ret; 
  ret = -1e9;

  if (a[x][i] <= a[x][i + 1]) ret = max(ret, f(c, x, i + 1)); 
  if (a[x][i] <= a[x ^ 1][i + 1]) ret = max(ret, f(c, x ^ 1, i + 1)); 
  ret += c == x; 
  return ret; 
}

int main() {
  scanf("%d", &n);

  for (int i = 0; i < 2; ++i) {
    for (int j = 1; j <= 2 * n; ++j) {
      scanf("%d", &a[i][j]);
    }
  }

  memset(dp, -1, sizeof dp);

  int p = 0, X = 0, Y = 0;

  auto extend = [&](int x, int i) {
    s[idx++] = x ? 'B' : 'A';
    p = a[x][i];
    x ? Y++ : X++;
  };

  for (int i = 1; i <= 2 * n; ++i) {
    if (X != n && p <= a[0][i] && X + f(0, 0, i) >= n && Y + f(1, 0, i) >= n) {
      extend(0, i); 
    } else if (Y != n && p <= a[1][i]) {
      extend(1, i); 
    } else {
      break;
    }
  }

  if (idx == 2 * n) {
    s[idx] = '\0';
    printf("%s\n", s);
  } else {
    puts("-1");
  }
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
building4.cpp:30:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &a[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~

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