Submission #215868

#	Time	Username	Problem	Language	Result	Execution time	Memory
215868		AlexPop28	Building 4 (JOI20_building4)	C++11	100 / 100	440 ms	119916 KiB

building4

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

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

  int n; cin >> n;
  vector<int> a(2 * n);
  for (int &x : a) cin >> x;
  vector<int> b(2 * n);
  for (int &x : b) cin >> x;

  // daca setam i pe A / B exista un interval compact de valori j
  // care sa reprezinte nr de alegeri B facute care sa respecte conditia
  // -> calculam minimul si maximul

  vector<vector<int>> min_dp(2 * n, vector<int>(2, -1));
  vector<vector<int>> max_dp(2 * n, vector<int>(2, -1));

  auto UpdateMin = [&](int i, int si, int j, int sj) {
    if (min_dp[j][sj] == -1) return;
    if (min_dp[i][si] == -1 || min_dp[i][si] > min_dp[j][sj] + (si == 1)) {
      min_dp[i][si] = min_dp[j][sj] + (si == 1);
    }
  };

  auto UpdateMax = [&](int i, int si, int j, int sj) {
    if (max_dp[j][sj] == -1) return;
    if (max_dp[i][si] == -1 || max_dp[i][si] < max_dp[j][sj] + (si == 1)) {
      max_dp[i][si] = max_dp[j][sj] + (si == 1);
    }
  };

  min_dp[0][0] = 0;
  max_dp[0][0] = 0;
  min_dp[0][1] = 1;
  max_dp[0][1] = 1;
  for (int i = 1; i < 2 * n; ++i) {
    // punem a daca se poate
    if (a[i] >= a[i - 1]) {
      UpdateMin(i, 0, i - 1, 0);
      UpdateMax(i, 0, i - 1, 0);
    }
    if (a[i] >= b[i - 1]) {
      UpdateMin(i, 0, i - 1, 1);
      UpdateMax(i, 0, i - 1, 1);
    }

//    dbg() name(i) name(min_dp[i][0]) name(max_dp[i][0]) endl;

    // punem b
    if (b[i] >= a[i - 1]) {
      UpdateMin(i, 1, i - 1, 0);
      UpdateMax(i, 1, i - 1, 0);
    }
    if (b[i] >= b[i - 1]) {
      UpdateMin(i, 1, i - 1, 1);
      UpdateMax(i, 1, i - 1, 1);
    }
    
//    dbg() name(i) name(min_dp[i][1]) name(max_dp[i][1]) endl;
  }

  auto Check = [&](int i, int si, int cnt) {
    return min_dp[i][si] <= cnt && cnt <= max_dp[i][si];
  };

  int lst = -1;
  if (Check(2 * n - 1, 0, n)) lst = 0;
  if (Check(2 * n - 1, 1, n)) lst = 1;

  if (lst == -1) {
    cout << "-1\n";
    return 0;
  }

  string ans;
  int cnt = n;
  for (int i = 2 * n - 1; i >= 0; --i) {
    ans += lst == 0 ? 'A' : 'B';
    cnt -= lst == 1;
    int curr = lst == 0 ? a[i] : b[i];
    if (i == 0) break;
    bool ok = false;
    if (curr >= a[i - 1] && Check(i - 1, 0, cnt)) {
      lst = 0;
      ok = true;
    }
    if (curr >= b[i - 1] && Check(i - 1, 1, cnt)) {
      lst = 1;
      ok = true;
    }
    assert(ok);
  }
  assert(cnt == 0);

  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  
//  vector<vector<vector<int>>> from(2 * n,
//    vector<vector<int>>(n + 1,
//      vector<int>(2, -1)));
//
//  // dp[i][cate_b][a / b]
//  from[0][0][0] = 1;
//  from[0][1][1] = 1;
//  for (int i = 1; i < 2 * n; ++i) {
//    for (int j = 0; j <= n; ++j) {
//      // punem din a
//      if (a[i] >= a[i - 1] && from[i - 1][j][0] != -1)
//        from[i][j][0] = 0;
//      if (a[i] >= b[i - 1] && from[i - 1][j][1] != -1)
//        from[i][j][0] = 1;
//
////      if (from[i][j][0] != -1) dbg() name(i) name(j) 0 << name(from[i][j][0]) endl;
////      if (from[i][j][0] != -1) {
////        dbg() name(i) name(j) endl;
////      }
//
//      if (j == 0) continue;
//      if (b[i] >= a[i - 1] && from[i - 1][j - 1][0] != -1)
//        from[i][j][1] = 0;
//      if (b[i] >= b[i - 1] && from[i - 1][j - 1][1] != -1)
//        from[i][j][1] = 1;
////      if (from[i][j][1] != -1) dbg() name(i) name(j) 1 << name(from[i][j][1]) endl;
//      if (from[i][j][1] != -1) {
//        dbg() name(i) name(j) endl;
//      }
//    }
//  }
//  int lst = -1;
//  if (from[2 * n - 1][n][0] != -1) lst = 0;
//  if (from[2 * n - 1][n][1] != -1) lst = 1;
//
//  if (lst == -1) {
//    cout << "-1\n";
//    return 0;
//  }
//  
//  string ans;
//  int cnt = n;
//  for (int i = 2 * n - 1; i >= 0; --i) {
//    ans += lst == 0 ? 'A' : 'B';
//    int curr = lst;
//    lst = from[i][cnt][lst];
//    cnt -= curr == 1; 
//  }
//  reverse(ans.begin(), ans.end());
//  cout << ans << endl;
  

}

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