Submission #211558

#	Time	Username	Problem	Language	Result	Execution time	Memory
211558		mcdx9524	Building 4 (JOI20_building4)	C++14	100 / 100	337 ms	26152 KiB

building4

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 5e5 + 7;
const int inf = 1e9 + 7;

pair <int, int> dp[2 * N][2];
int a[2 * N][2];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  n *= 2;
  for (int i = 0; i < n; i++) {
    cin >> a[i][0];
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i][1];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      dp[i][j] = {inf, -1};
    }
  }
  dp[0][0] = {1, 1};
  dp[0][1] = {0, 0};
  for (int i = 1; i < n; i++) {
    for (int me = 0; me < 2; me++) {
      for (int was = 0; was < 2; was++) {
        if (a[i - 1][was] > a[i][me]) {
          continue;
        }
        dp[i][me].first = min(dp[i][me].first, dp[i - 1][was].first + (me == 0));
        dp[i][me].second = max(dp[i][me].second, dp[i - 1][was].second + (me == 0));
      }
    }
  }
  int need = n / 2;
  string ans;
  if (dp[n - 1][0].first > need || dp[n - 1][0].second < need) {
    if (dp[n - 1][1].first > need || dp[n - 1][1].second < need) {
      cout << -1 << '\n';
      return 0;
    }
  }
  int need_a = need, need_b = need;
  int last = inf;
  for (int i = n - 1; i >= 0; i--) {
    if (dp[i][0].first <= need_a && dp[i][0].second >= need_a && a[i][0] <= last) {
      ans += 'A';
      need_a--;
      last = a[i][0];
    } else {
      ans += 'B';
      need_b--;
      last = a[i][1];
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
  return 0;
}

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