Submission #231801

#	Time	Username	Problem	Language	Result	Execution time	Memory
231801		summitwei	Building 4 (JOI20_building4)	C++17	100 / 100	1263 ms	45460 KiB

building4

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

#define F0R(i, a) for(int i=0; i<a; i++)
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define RFOR(i, b, a) for(int i=b; i>=a; i--)

#define f first
#define s second
#define pb push_back

#define INF 0x3f3f3f3f
#define MOD 998244353LL

#define MN 1000005
int n;
int a[MN], b[MN];
pii rg[MN][2]; //# A chosen, min-max

int main(){
    cin >> n;
    FOR(i, 1, 2*n) cin >> a[i];
    FOR(i, 1, 2*n) cin >> b[i];
    FOR(i, 1, 2*n) rg[i][0] = rg[i][1] = {INF, -INF};

    FOR(i, 1, 2*n){
        if(a[i] >= a[i-1]){
            rg[i][0].f = min(rg[i][0].f, rg[i-1][0].f+1);
            rg[i][0].s = max(rg[i][0].s, rg[i-1][0].s+1);
        }
        if(a[i] >= b[i-1]){
            rg[i][0].f = min(rg[i][0].f, rg[i-1][1].f+1);
            rg[i][0].s = max(rg[i][0].s, rg[i-1][1].s+1);
        }
        if(b[i] >= a[i-1]){
            rg[i][1].f = min(rg[i][1].f, rg[i-1][0].f);
            rg[i][1].s = max(rg[i][1].s, rg[i-1][0].s);
        }
        if(b[i] >= b[i-1]){
            rg[i][1].f = min(rg[i][1].f, rg[i-1][1].f);
            rg[i][1].s = max(rg[i][1].s, rg[i-1][1].s);
        }
    }
    int onA, cur=n;
    if(rg[2*n][0].f <= n && rg[2*n][0].s >= n){
        onA = true;
    } else if(rg[2*n][1].f <= n && rg[2*n][1].s >= n){
        onA = false;
    } else{
        cout << "-1\n";
        return 0;
    }
    string s;
    RFOR(i, 2*n, 1){
        if(onA) s.pb('A');
        else s.pb('B');
        if(onA){
            --cur;
            if(a[i-1] <= a[i] && rg[i-1][0].f <= cur && cur <= rg[i-1][0].s){
                onA = true;
            } else if(b[i-1] <= a[i] && rg[i-1][1].f <= cur && cur <= rg[i-1][1].s){
                onA = false;
            } else{
                assert(false);
            }
        } else{
            if(a[i-1] <= b[i] && rg[i-1][0].f <= cur && cur <= rg[i-1][0].s){
                onA = true;
            } else if(b[i-1] <= b[i] && rg[i-1][1].f <= cur && cur <= rg[i-1][1].s){
                onA = false;
            } else{
                assert(false);
            }
        }
    }
    reverse(s.begin(), s.end());
    cout << s << "\n";

    return 0;
}

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