Submission #945118

#	Time	Username	Problem	Language	Result	Execution time	Memory
945118		vjudge1	Building 4 (JOI20_building4)	C++17	100 / 100	194 ms	46928 KiB

building4

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 1e6;
const int A = 0;
const int B = 1;

int dpmin[NMAX + 2][2];
int dpmax[NMAX + 2][2];
int pmin[NMAX + 2];
int pmax[NMAX + 2];

int a[NMAX + 2], b[NMAX + 2];

int main() {
#ifndef LOCAL
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
#endif

  int n;
  std::cin >> n;
  n *= 2;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    std::cin >> b[i];
  }

  for (int i = 1; i <= n; i++) {
    dpmin[i][A] = dpmin[i][B] = 1e9;
    dpmax[i][A] = dpmax[i][B] = -1e9;
  }

  for (int i = 1; i <= n; i++) {
    if (a[i] >= a[i - 1]) {
      dpmin[i][A] = std::min(dpmin[i][A], dpmin[i - 1][A]);
      dpmax[i][A] = std::max(dpmax[i][A], dpmax[i - 1][A]);
    }
    if (a[i] >= b[i - 1]) {
      dpmin[i][A] = std::min(dpmin[i][A], dpmin[i - 1][B]);
      dpmax[i][A] = std::max(dpmax[i][A], dpmax[i - 1][B]);
    }
    if (b[i] >= a[i - 1]) {
      dpmin[i][B] = std::min(dpmin[i][B], dpmin[i - 1][A] + 1);
      dpmax[i][B] = std::max(dpmax[i][B], dpmax[i - 1][A] + 1);
    }
    if (b[i] >= b[i - 1]) {
      dpmin[i][B] = std::min(dpmin[i][B], dpmin[i - 1][B] + 1);
      dpmax[i][B] = std::max(dpmax[i][B], dpmax[i - 1][B] + 1);
    }
  }

  int m = n / 2;

  if ((dpmin[n][A] <= m && m <= dpmax[n][A]) || (dpmin[n][B] <= m && m <= dpmax[n][B])) {
    std::string answer(n + 1, 'A');
    int c;
    if (dpmin[n][A] <= m && m <= dpmax[n][A]) {
      c = A;
    } else {
      c = B;
    }
    for (int i = n; i > 0; i--) {
      if (c == A) {
        if (a[i] >= a[i - 1]) {
          if (dpmin[i - 1][A] <= m && m <= dpmax[i - 1][A]) {
            c = A;
            continue;
          }
        }
        c = B;
      } else {
        m--;
        answer[i] = 'B';
        if (b[i] >= b[i - 1]) {
          if (dpmin[i - 1][B] <= m && m <= dpmax[i - 1][B]) {
            c = B;
            continue;
          }
        }
        c = A;
      }
    }
    answer.erase(answer.begin());
    std::cout << answer;
  } else {
    std::cout << -1;
  }

  return 0;
}

Compilation message (stderr)

building4.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

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