Submission #1311748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311748		vedchoudhary	Building 4 (JOI20_building4)	C++20	0 / 100	2 ms	580 KiB

building4

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

using namespace std;

using ll = long long;
#define int ll

void fail() {
    cout << -1;
    exit(0);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    vector<int> a(2*n); for(int i = 0; i < 2*n; i++) cin >> a[i];
    vector<int> b(2*n); for(int i = 0; i < 2*n; i++) cin >> b[i];
    vector<int> mx(2*n); for(int i = 0; i < 2*n; i++) mx[i] = max(a[i],b[i]);
    vector<int> mn(2*n); for(int i = 0; i < 2*n; i++) mn[i] = min(a[i],b[i]);
    vector<int> mnPoss(2*n);
    mnPoss[0] = mn[0];
    for(int i = 1; i < 2*n; i++) {
        if(mnPoss[i-1]>mx[i]) fail();
        else if(mnPoss[i-1]<=mn[i]) mnPoss[i] = mn[i];
        else mnPoss[i] = mx[i];
    }
    vector<int> mxPoss(2*n);
    mxPoss[2*n-1] = mx[2*n-1];
    for(int i = 2*n-2; i >= 0; i--) {
        if(mxPoss[i+1]<mn[i]) fail();
        else if(mxPoss[i+1]>=mx[i]) mxPoss[i] = mx[i];
        else mxPoss[i] = mn[i];
    }
    int ac = 0;
    int bc = 0;
    int jc = 0;
    vector<int> c(2*n);
    for(int i = 0; i < 2*n; i++) {
        if(mnPoss[i]>mxPoss[i]) fail();
        if(mnPoss[i]<=a[i]&&a[i]<=mxPoss[i]&&mnPoss[i]<=b[i]&&b[i]<=mxPoss[i]) { jc++; c[i] = 2; }
        else {
            if(mnPoss[i]<=a[i]&&a[i]<=mxPoss[i]) { ac++; c[i] = 0; }
            else if(mnPoss[i]<=b[i]&&b[i]<=mxPoss[i]) { bc++; c[i] = 1; }
        }
    }
    if(ac>n||bc>n||ac+jc<n||bc+jc<n) fail();
    int an = n - ac;
    int bn = n - bc;
    int fan = 0; int ban = 0;
    string ans; ans.reserve(2*n);
    for(int i = 0; i < 2*n; i++) {
        if(c[i]==0) { ans.push_back('A'); fan++; }
        else if(c[i]==1) { ans.push_back('B'); ban++; }
        else {
            if(an>bn) { ans.push_back('A'); an--; fan++; }
            else { ans.push_back('B'); bn--; ban++; }
        }
    }
    if(fan==n&&ban==n) cout << ans;
    else fail();
    return 0;
}

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