Submission #482459

#	Time	Username	Problem	Language	Result	Execution time	Memory
482459		SirCovidThe19th	Building 4 (JOI20_building4)	C++17	100 / 100	767 ms	45516 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e6 + 5;

int n, A[mx][2]; pii dp[mx][2]; 

int main(){
    cin >> n; n *= 2; 
    FOR(i, 1, n + 1) cin >> A[i][0];
    FOR(i, 1, n + 1) cin >> A[i][1];

    dp[0][0] = dp[0][1] = {0, 0};
    FOR(i, 1, n + 1) FOR(k, 0, 2){
        dp[i][k] = {1e9, -1e9};
        FOR(prv, 0, 2) if (A[i][k] >= A[i - 1][prv]){
            dp[i][k].f = min(dp[i][k].f, dp[i - 1][prv].f + !k);
            dp[i][k].s = max(dp[i][k].s, dp[i - 1][prv].s + !k);
        }
    }
    vector<char> ans; int cnt = n / 2, cur = -1;
    for (int i = n; i; i--){
        auto ok = [&](int use){ 
            return (cnt >= dp[i][use].f and cnt <= dp[i][use].s) and 
                   (cur == -1 or A[i][use] <= A[i + 1][cur]); 
        };
        if (ok(0)) ans.push_back('A'), cnt--, cur = 0;
        else if (ok(1)) ans.push_back('B'), cur = 1;
        else{ cout<<-1<<endl; return 0; }
    }
    reverse(ans.begin(), ans.end());
    for (char ret : ans) cout<<ret;
}

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