Submission #1276921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276921		nanaseyuzuki	Building 4 (JOI20_building4)	C++20	100 / 100	161 ms	26048 KiB

building4

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 5e5 + 5, inf = 1e9;

int n, a[mn << 1], b[mn << 1], dp_min[mn << 1][2], dp_max[mn << 1][2];

void solve(){
    cin >> n;
    for(int i = 1; i <= n << 1; i++) cin >> a[i];
    for(int i = 1; i <= n << 1; i++) cin >> b[i];
    fill(&dp_min[0][0], &dp_min[0][0] + (mn << 2), inf);
    dp_min[0][1] = dp_min[0][0] = 0;
    for(int i = 1; i <= n << 1; i++){
        if(a[i] >= a[i - 1]){
            dp_min[i][0] = min(dp_min[i][0], dp_min[i - 1][0]);
            dp_max[i][0] = max(dp_max[i][0], dp_max[i - 1][0]);
        }
        if(a[i] >= b[i - 1]){
            dp_min[i][0] = min(dp_min[i][0], dp_min[i - 1][1]);
            dp_max[i][0] = max(dp_max[i][0], dp_max[i - 1][1]);
        }
        if(b[i] >= a[i - 1]){
            dp_min[i][1] = min(dp_min[i][1], dp_min[i - 1][0] + 1);
            dp_max[i][1] = max(dp_max[i][1], dp_max[i - 1][0] + 1);
        }
        if(b[i] >= b[i - 1]){
            dp_min[i][1] = min(dp_min[i][1], dp_min[i - 1][1] + 1);
            dp_max[i][1] = max(dp_max[i][1], dp_max[i - 1][1] + 1);
        }
    }
    bool ok = false, ed = - 1;
    if(dp_min[n << 1][0] <= n && dp_max[n << 1][0] >= n){
        ed = 0;
        ok = true;
    }
    if(dp_min[n << 1][1] <= n && dp_max[n << 1][1] >= n){
        ed = 1;
        ok = true;
    }
    if(!ok){
        cout << -1 << '\n';
        return;
    }
    int pos = 2 * n, lef = n;
    string s;
    while(pos){
        if(ed){
            s += 'B';
            // cout << "B " << b[pos] << '\n';
            lef --;
            if(b[pos - 1] <= b[pos] && dp_min[pos - 1][1] <= lef && dp_max[pos - 1][1] >= lef) ed = 1;
            else ed = 0;
        }
        else{
            s += 'A';
            // cout << "A " << a[pos] << '\n';
            if(b[pos - 1] <= a[pos] && dp_min[pos - 1][1] <= lef && dp_max[pos - 1][1] >= lef) ed = 1;
            else ed = 0;
        }
        pos --;
    }
    reverse(all(s));
    cout << s << '\n';
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

building4.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

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