제출 #910155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
910155		vjudge1	건물 4 (JOI20_building4)	C++17	100 / 100	259 ms	44752 KiB

building4

#include <bits/stdc++.h>
using namespace std; 
const int nx=5e5+5;
int n, a[2*nx], b[2*nx], dp[2][2*nx][2], c, x; 
int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=2*n; i++) cin>>a[i];
    for (int i=1; i<=2*n; i++) cin>>b[i];
    dp[0][1][0]=dp[0][1][1]=1;
    for (int i=2; i<=2*n; i++){
        dp[0][i][0]=dp[1][i][0]=1e9;
        dp[0][i][1]=dp[1][i][1]=-1e9;
        if (a[i]>=a[i-1]) dp[0][i][0]=min(dp[0][i][0], dp[0][i-1][0]+1), dp[0][i][1]=max(dp[0][i][1], dp[0][i-1][1]+1);
        if (a[i]>=b[i-1]) dp[0][i][0]=min(dp[0][i][0], dp[1][i-1][0]+1), dp[0][i][1]=max(dp[0][i][1], dp[1][i-1][1]+1);
        if (b[i]>=a[i-1]) dp[1][i][0]=min(dp[1][i][0], dp[0][i-1][0]), dp[1][i][1]=max(dp[1][i][1], dp[0][i-1][1]);
        if (b[i]>=b[i-1]) dp[1][i][0]=min(dp[1][i][0], dp[1][i-1][0]), dp[1][i][1]=max(dp[1][i][1], dp[1][i-1][1]);
    }
    vector<bool> ans;
    if (dp[0][2*n][0]<=n&&n<=dp[0][2*n][1]) x=n-1, c=0, ans.push_back(0);
    else if (dp[1][2*n][0]<=n&&n<=dp[1][2*n][1]) x=n, c=1, ans.push_back(1);
    else return cout<<-1, 0;
    for (int i=2*n-1; i>=1; i--){
        if (dp[0][i][0]<=x&&x<=dp[0][i][1]&&a[i]<=(c?b[i+1]:a[i+1])) --x, c=0, ans.push_back(0);
        else ans.push_back(1), c=1;
    }
    for (int i=2*n-1; i>=0; i--) cout<<(ans[i]?'B':'A');
}

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