제출 #366399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366399		Kazalika	건물 4 (JOI20_building4)	C++14	100 / 100	299 ms	45536 KiB

building4

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 7, inf = 1e9 + 9;
 
int n, a[N][2];
int mn[N][2], mx[N][2];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= 2 * n; ++i)
    cin >> a[i][0];
  for (int i = 1; i <= 2 * n; ++i)
    cin >> a[i][1];
  for (int i = 1; i <= 2 * n; i++) {
   mn[i][0] = mn[i][1] = inf;
   mx[i][0] = mx[i][1] = -inf;
  }
  for (int i = 1; i <= 2 * n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        if (a[i - 1][k] <= a[i][j]) {
          if (mn[i - 1][k] != inf)
            mn[i][j] = min(mn[i][j], mn[i - 1][k] + j);
          if (mx[i - 1][k] != -inf)
            mx[i][j] = max(mx[i][j], mx[i - 1][k] + j);
        }
      }
    }
  }
  int j = -1;
  for (int i = 0; i < 2; i++) {
    if (mn[2 * n][i] <= n && n <= mx[2 * n][i]) {
      j = i;
      break;
    }
  }
  if (j == -1) {
    cout << -1;
    return 0;
  }
  string ans;
  int cur = n;
  for (int i = 2 * n; i; i--) {
    cur -= j;
    ans.push_back('A' + j);
    int jj = -1;
    for (int k = 0; k < 2; k++) {
      if (mn[i - 1][k] <= cur && cur <= mx[i - 1][k] && a[i - 1][k] <= a[i][j]) {
        jj = k;
        break;
      }
    }
    j = jj;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}

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