oj.uz

Submission #480693

# Submission time Handle Problem Language Result Execution time Memory
480693 2021-10-17T20:01:44 Z jesus_coconut Building 4 (JOI20_building4) C++17
0 / 100
 2 ms 332 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -