Submission #930854

#	Time	Username	Problem	Language	Result	Execution time	Memory
930854		ksujay2	Building 4 (JOI20_building4)	C++17	100 / 100	218 ms	48208 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, b) for(int i = 0; i < (b); i++)
#define R0F(i, b) for(int i = (b) - 1; i >= 0; i--)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); i--)
using pi = pair<int, int>;
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int N; cin >> N;
  vector<int> A(2 * N), B(2 * N);
  F0R(i, 2 * N) cin >> A[i];
  F0R(i, 2 * N) cin >> B[i];
  vector<array<pi, 2>> dp(2 * N, {{{1e9, -1e9}, {1e9, -1e9}}});
  dp[0][0] = {1, 1};
  dp[0][1] = {-1, -1};
  FOR(i, 1, 2 * N) {
    if(A[i - 1] <= A[i]) {
      dp[i][0].second = max(dp[i][0].second, dp[i - 1][0].second + 1);
      dp[i][0].first = min(dp[i][0].first, dp[i - 1][0].first + 1);
    }
    if(A[i - 1] <= B[i]) {
      dp[i][1].second = max(dp[i][1].second, dp[i - 1][0].second - 1);
      dp[i][1].first = min(dp[i][1].first, dp[i - 1][0].first - 1);
    }
    if(B[i - 1] <= A[i]) {
      dp[i][0].second = max(dp[i][0].second, dp[i - 1][1].second + 1);
      dp[i][0].first = min(dp[i][0].first, dp[i - 1][1].first + 1);
    }
    if(B[i - 1] <= B[i]) {
      dp[i][1].second = max(dp[i][1].second, dp[i - 1][1].second - 1);
      dp[i][1].first = min(dp[i][1].first, dp[i - 1][1].first - 1);
    }
  }
  vector<int> choice(2 * N);
  int sum = 0;
  int lv = 1e9;
  ROF(i, 0, 2 * N) {
    if(lv >= A[i] && dp[i][0].second >= -sum && -sum >= dp[i][0].first) {
      choice[i] = 0;
      lv = A[i];
      sum++;
    } else if(lv >= B[i] && dp[i][1].second >= -sum && -sum >= dp[i][1].first) {
      choice[i] = 1;
      lv = B[i];
      sum--;
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  F0R(i, 2 * N) {
    if(choice[i] == 0) cout << 'A';
    else cout << 'B';
  }
}

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