Submission #480693

#	Time	Username	Problem	Language	Result	Execution time	Memory
480693		jesus_coconut	Building 4 (JOI20_building4)	C++17	0 / 100	2 ms	332 KiB

building4

#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int const MOD = 1e9 + 7;

void solve() {
  int n;
  cin >> n;
  array<vi, 2> a;
  a[0].resize(2 * n);
  a[1].resize(2 * n);
  for (auto &it: a[0]) cin >> it;
  for (auto &it: a[1]) cin >> it;
  vi mn(2 * n), mx(2 * n);
  mn[0] = a[1][0] < a[0][0];
  for (int i = 1; i < 2 * n; ++i) {
    if (a[0][i] <= a[1][i]) {
      if (a[mn[i - 1]][i - 1] <= a[0][i]) {
        mn[i] = 0;
      } else if (a[mn[i - 1]][i - 1] <= a[1][i]) {
        mn[i] = 1;
      } else {
        cout << "-1\n";
        return;
      }
    } else {
      if (a[mn[i - 1]][i - 1] <= a[1][i]) {
        mn[i] = 1;
      } else if (a[mn[i - 1]][i - 1] <= a[0][i]) {
        mn[i] = 0;
      } else {
        cout << "-1\n";
        return;
      }
    }
  }
  mx.back() = a[1].back() > a[0].back();
  for (int i = 2 * n - 2; i >= 0; --i) {
    if (a[1][i] >= a[0][i]) {
      if (a[mx[i + 1]][i + 1] >= a[1][i]) {
        mx[i] = 1;
      } else if (a[mx[i + 1]][i + 1] >= a[0][i]) {
        mx[i] = 0;
      } else {
        cout << "-1\n";
        return;
      }
    } else {
      if (a[mx[i + 1]][i + 1] >= a[0][i]) {
        mx[i] = 0;
      } else if (a[mx[i + 1]][i + 1] >= a[1][i]) {
        mx[i] = 1;
      } else {
        cout << "-1\n";
        return;
      }
    }
  }
  int s1 = accumulate(all(mn), 0);
  int s2 = accumulate(all(mx), 0);
  if (min(s1, s2) > n || max(s1, s2) < n) {
    cout << "-1\n";
    return;
  }
  int curr = 0;
  int ans = 0;
  for (; ans < 2 * n; ++ans) {
    if (curr + s2 == n) break;
    curr += mn[ans];
    s2 -= mx[ans];
  }
  for (int i = 0; i < ans; ++i) {
    cout << "AB"[mn[i]];
  }
  for (int i = ans; i < 2 * n; ++i) {
    cout << "AB"[mx[i]];
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

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