Submission #1126688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126688		Zero_OP	Building 4 (JOI20_building4)	C++20	100 / 100	233 ms	35236 KiB

building4

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 1e6 + 5;
const int inf = 1e9;

int N, a[MAX], b[MAX], result[MAX];
pair<int, int> dp[MAX][2]; //nA - nB

void update(pair<int, int>& a, const pair<int, int>& b, int v){
    a.first = min(a.first, b.first + v);
    a.second = max(a.second, b.second + v);
}

int eval(int i, int lst){
    return (lst ? b[i] : a[i]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    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[1][0] = {1, 1};
    dp[1][1] = {-1, -1};

    for(int i = 2; i <= 2 * N; ++i){
        dp[i][0] = {inf, -inf};
        dp[i][1] = {inf, -inf};

        if(a[i - 1] <= a[i]) update(dp[i][0], dp[i - 1][0], +1);
        if(b[i - 1] <= a[i]) update(dp[i][0], dp[i - 1][1], +1);
        if(a[i - 1] <= b[i]) update(dp[i][1], dp[i - 1][0], -1);
        if(b[i - 1] <= b[i]) update(dp[i][1], dp[i - 1][1], -1);
    }

    int target = 0, lst = 1e9;
    for(int i = 2 * N; i >= 1; --i){
        if(dp[i][0].first <= target && target <= dp[i][0].second && a[i] <= lst){
            --target;
            result[i] = 0;
            lst = a[i];
        } else if(dp[i][1].first <= target && target <= dp[i][1].second && b[i] <= lst){
            ++target;
            result[i] = 1;
            lst = b[i];
        } else{
            cout << -1 << '\n';
            return 0;
        }
    }

    assert(target == 0);
    for(int i = 1; i <= 2 * N; ++i) cout << (result[i] ? 'B' : 'A');

    return 0;
}

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