Submission #211800

#	Time	Username	Problem	Language	Result	Execution time	Memory
211800		grt	Building 4 (JOI20_building4)	C++17	100 / 100	336 ms	31596 KiB

building4

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
#define _ ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;

const int nax = 1000*1000+10,INF=1e9+10;
int n;
int a[nax], b[nax];
pi dp[nax][2];

int main() {_
    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] = dp[0][0] = {0,0};
    for(int i=1; i<=2*n; i++) {
        dp[i][0] = dp[i][1] = {INF,-INF};
        if(a[i]>=a[i-1]) {
            dp[i][0] = {min(dp[i][0].ST,dp[i-1][0].ST+1),max(dp[i][0].ND,dp[i-1][0].ND+1)};
        }
        if(a[i]>=b[i-1]) {
            dp[i][0] = {min(dp[i][0].ST,dp[i-1][1].ST+1),max(dp[i][0].ND,dp[i-1][1].ND+1)};
        }
        if(b[i]>=b[i-1]) {
            dp[i][1] = {min(dp[i][1].ST,dp[i-1][1].ST),max(dp[i][1].ND,dp[i-1][1].ND)};
        }
        if(b[i]>=a[i-1]) {
            dp[i][1] = {min(dp[i][1].ST,dp[i-1][0].ST),max(dp[i][1].ND,dp[i-1][0].ND)};
        }
    }
    int x = 2*n, y = n, last = INF;
    bool ok = 1;
    string ans = "";
    while(x>0) {
        if(dp[x][0].ST<=y&&y<=dp[x][0].ND&&a[x]<=last) {
            last = a[x];
            x--;
            y--;
            ans+="A";
        } else if(dp[x][1].ST<=y&&y<=dp[x][1].ND&&b[x]<=last) {
            last = b[x];
            x--;
            ans+="B";
        } else {
            ok = 0;
            break;
        }
    }
    if(!ok) {
        cout<<"-1";
        return 0;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
}

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