Submission #944972

#	Time	Username	Problem	Language	Result	Execution time	Memory
944972		vjudge1	Building 4 (JOI20_building4)	C++17	0 / 100	19 ms	10720 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;

int dpmin[NMAX + 2];
int dpmax[NMAX + 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] = 1e9;
  }

  for (int i = 1; i <= n; i++) {
    bool ok = true;
    dpmax[i] = -1e9;
    for (int j = i - 1; j >= 0 && ok; j--) {
      if (j != i - 1) {
        ok &= (a[j] <= a[j + 1]);
      }
      if (b[i] >= b[j]) {
        if (j != i - 1) {
          if (a[i - 1] > b[i]) {
            break;
          }
          if (b[j] > a[j + 1]) {
            continue;
          }
        }
        if (dpmin[j] + 1 <= dpmin[i]) {
          dpmin[i] = dpmin[j] + 1;
          pmin[i] = j;
        }
        if (dpmax[j] + 1 >= dpmax[i]) {
          dpmax[i] = dpmax[j] + 1;
          pmax[i] = j;
        }
      }
    }
  }

  int m = n / 2;

  bool incr = true;

//  for (int i = 1; i <= n; i++) {
//    std::cout << i << ": " << dpmin[i] << " <> " << dpmax[i] << '\n';
//  }
//
//  for (int i = 1; i <= n; i++) {
//    std::cout << i << ": " << pmin[i] << " <> " << pmax[i] << '\n';
//  }

  for (int i = n; i > 0 && incr; i--) {
    if (i <= n - 2) {
      incr &= (a[i + 1] <= a[i + 2]);
    }
    if (!incr) {
      break;
    }
    if (dpmin[i] <= m && m <= dpmax[i] && (i == n || b[i] <= a[i + 1])) {
      int p = i;
      int cntB = 0;
      std::string answer(n + 1, 'A');
      while (p > 0) {
        cntB++;
        answer[p] = 'B';
        p = pmin[p];
      }
      p = i;
      while (cntB < m) {
//        std::cout << "! " << p << ' ' << dpmax[i] << '\n';
        if (answer[p] == 'A') {
          cntB++;
          answer[p] = 'B';
        }
        p = pmax[p];
      }
      answer.erase(answer.begin());
      std::cout << answer;
      return 0;
    }
  }

  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: 0 / 11
• Subtask 2: 0 / 89