Submission #1225003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225003		Gray	Building 4 (JOI20_building4)	C++20	100 / 100	173 ms	49512 KiB

building4

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

void solve(){
    ll n; cin >> n; n*=2;
    vector<array<ll, 2>> a(n);
    for (ll i=0; i<n; i++) cin >> a[i][0];
    for (ll i=0; i<n; i++) cin >> a[i][1];
    array<ll, 2> inf = {INF, -INF};
    vector<array<array<ll, 2>, 2>> dp(n, {inf, inf});
    dp[0][0][0] = dp[0][0][1] = 1;
    dp[0][1][0] = dp[0][1][1] = -1;
    for (ll i=1; i<n; i++){
        for (ll j=0; j<2; j++){
            if (a[i][j]>=a[i-1][0]){
                dp[i][j][0]=min(dp[i][j][0], dp[i-1][0][0]+(j==0?1:-1));
                dp[i][j][1]=max(dp[i][j][1], dp[i-1][0][1]+(j==0?1:-1));
            }
            if (a[i][j]>=a[i-1][1]){
                dp[i][j][0]=min(dp[i][j][0], dp[i-1][1][0]+(j==0?1:-1));
                dp[i][j][1]=max(dp[i][j][1], dp[i-1][1][1]+(j==0?1:-1));
            }
        }
    }
    if ((dp[n-1][0][0]<=0 and dp[n-1][0][1]>=0) or (dp[n-1][1][0]<=0 and dp[n-1][1][1]>=0)){
        ll cur=0; string s = "";
        ll prev=INF;
        for (ll i=n-1; i>=0; i--){
            if (dp[i][0][0]<=cur and dp[i][0][1]>=cur and prev>=a[i][0]){
                cur--; s+='A'; prev=a[i][0];
            }else{
                cur++; s+='B'; prev=a[i][1];
            }
        }
        reverse(s.begin(), s.end());
        cout << s << ln;
    } else {
        cout << -1 << ln;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) solve();
}

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