Submission #998839

#	Time	Username	Problem	Language	Result	Execution time	Memory
998839		snpmrnhlol	Building 4 (JOI20_building4)	C++17	100 / 100	518 ms	45328 KiB

building4

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5;
const int inf = 2e9;
int v[2*N][2];
pair<int,int> dp[2*N][2];
bool ans[2*N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < 2*n;i++){
        cin>>v[i][0];
    }
    for(int i = 0;i < 2*n;i++){
        cin>>v[i][1];
    }
    for(int i = 2*n - 1;i >= 0;i--){
        dp[i][0] = {inf,-inf};
        dp[i][1] = {inf,-inf};
        if(i == 2*n - 1){
            dp[i][0] = {0,0};
            dp[i][1] = {1,1};
        }else{
            for(int j = 0;j < 2;j++){
                for(int k = 0;k < 2;k++){
                    if(v[i][j] <= v[i + 1][k]){
                        dp[i][j].first = min(dp[i][j].first,dp[i + 1][k].first + j);
                        dp[i][j].second = max(dp[i][j].second,dp[i + 1][k].second + j);
                    }
                }
            }
        }
        //cout<<dp[i][0].first<<' '<<dp[i][0].second<<' '<<dp[i][1].first<<' '<<dp[i][1].second<<'\n';
    }
    int target = n;
    int prv = -1;
    if(dp[0][0].first <= target && target <= dp[0][0].second)prv = 0;
    if(dp[0][1].first <= target && target <= dp[0][1].second)prv = 1;
    if(prv == -1){
        cout<<-1;
    }else{
        ans[0] = prv;
        target-=prv;
        for(int i = 1;i < 2*n;i++){
            int cur = -1;
            if(dp[i][0].first <= target && target <= dp[i][0].second && v[i - 1][prv] <= v[i][0])cur = 0;
            if(dp[i][1].first <= target && target <= dp[i][1].second && v[i - 1][prv] <= v[i][1])cur = 1;
            ans[i] = cur;
            target-=cur;
            prv = cur;
        }
        for(int i = 0;i < 2*n;i++){
            cout<<(ans[i] == 1?'B':'A');
        }
    }
    return 0;
}
/**
2
39 69 61 90
63 58 71 78
**/

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