Submission #384425

#	Time	Username	Problem	Language	Result	Execution time	Memory
384425		Sorting	Building 4 (JOI20_building4)	C++17	100 / 100	304 ms	58860 KiB

building4

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int N = 1e6 + 3;

pair<int, int> dp[N][2];
int n, a[N][2];

pair<int, int> merge(const pair<int, int> &l, const pair<int, int> &r){
    if(l == pair{1, 0} || r == pair{1, 0}) return (l == pair{1, 0}) ? r : l;
    return {min(l.first, r.first), max(l.second, r.second)};
}

void output(int i, int j, int target = n / 2){
    if(i == 0) return;
    target -= j;
    if(dp[i - 1][0].first <= target && target <= dp[i - 1][0].second && a[i - 1][0] <= a[i][j])
        output(i - 1, 0, target);
    else
        output(i - 1, 1, target);
    
    cout << (j ? "B" : "A");
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    n *= 2;
    for(int i = 1; i <= n; ++i) cin >> a[i][0];
    for(int i = 1; i <= n; ++i) cin >> a[i][1];

    dp[1][0] = {0, 0};
    dp[1][1] = {1, 1};

    for(int i = 2; i <= n; ++i)
        for(int j = 0; j <= 1; ++j){
            auto &ans = dp[i][j];
            ans = {1, 0};
            if(a[i - 1][0] <= a[i][j])
                ans = merge(ans, dp[i - 1][0]);
            if(a[i - 1][1] <= a[i][j])
                ans = merge(ans, dp[i - 1][1]);
            if(ans != pair{1, 0} && j){
                ans.first++;
                ans.second++;
            }
            //cout << ans.first << " " << ans.second << " - " << i << " " << j << endl; 
        }

    if(dp[n][0].first <= n / 2 && n / 2 <= dp[n][0].second)
        output(n, 0);
    else if(dp[n][1].first <= n / 2 && n / 2 <= dp[n][1].second)
        output(n, 1);
    else
        cout << "-1";
}

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