Submission #1290642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290642		reginox	Building 4 (JOI20_building4)	C++20	100 / 100	159 ms	25920 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e6+3;
int a[N][2], n;
pair<int, int> dp[N][2];
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(int i = 0; i < 2; i++){
    for(int j = 1; j <= n*2; j++) cin >> a[j][i];
  }
  for(int j = 1; j <= n * 2; j++){
    for (int i = 0; i < 2; i++){
      dp[j][i] = {1e9, -1e9};
      for(int u = 0; u <= 1; u++){
        if(a[j-1][u] <= a[j][i]){
          dp[j][i].first = min(dp[j][i].first, dp[j-1][u].first + i);
          dp[j][i].second = max(dp[j][i].second, dp[j-1][u].second + i);
        }
      }
    }
  }
  if (!(dp[n * 2][0].first <= n && n <= dp[n * 2][0].second) 
      && !(dp[n * 2][1].first <= n && n <= dp[n * 2][1].second)){
      cout << -1;
      return 0;
  }
  bool cur = 0;
  int cnt = n;
  a[n * 2 + 1][0] = 1e9;
  string ans;
  for(int i = n * 2; i >= 1; i--){
    for(int j = 0; j <= 1; j++){
      if(a[i + 1][cur] >= a[i][j] && dp[i][j].first <= cnt && cnt <= dp[i][j].second){
        cur = j;
        break;
      }
    }
    ans += 'A' + cur;
    cnt -= cur;
  }
  reverse(all(ans));
  cout << ans;
  return 0;
}

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