Submission #211802

#	Time	Username	Problem	Language	Result	Execution time	Memory
211802		achvanov	건물 4 (JOI20_building4)	C++17	100 / 100	321 ms	26988 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;
int a[N][2];
int dp[N][2][2];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int n;
  cin >> n;
  for (int j = 0; j < 2; ++j) {
    for (int i = 0; i < 2 * n; ++i) {
      cin >> a[i][j];
    }
  }
  dp[0][0][0] = dp[0][0][1] = 1;
  for (int i = 1; i < 2 * n; ++i) {
    for (int j = 0; j < 2; ++j) {
      dp[i][j][0] = 1e9;
      dp[i][j][1] = -1e9;
      for (int k = 0; k < 2; ++k) {
        if (a[i - 1][k] > a[i][j]) {
          continue;
        }
        dp[i][j][0] = min(dp[i][j][0], dp[i - 1][k][0] + (j ^ 1));
        dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + (j ^ 1));
      }
    }
  }
  for (int it = 0; it < 2; ++it) {
    if (dp[2 * n - 1][it][0] > n or dp[2 * n - 1][it][1] < n) {
      continue;
    }
    string ans;
    ans += char('A' + it);
    int tot = n - (it ^ 1);
    for (int i = 2 * n - 2; i >= 0; --i) {
      for (int j = 0; j < 2; ++j) {
        if (a[i][j] <= a[i + 1][it] and dp[i][j][0] <= tot and tot <= dp[i][j][1] and tot >= (j ^ 1)) {
          ans += char('A' + j);
          tot -= (j ^ 1);
          it = j;
          break;
        }
      }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
    return 0;
  }
  cout << -1;

  return 0;
}

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