Submission #782980

#	Time	Username	Problem	Language	Result	Execution time	Memory
782980		Josia	Building 4 (JOI20_building4)	C++17	100 / 100	192 ms	49476 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define int int64_t


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

    int n; cin >> n;

    n*=2;

    vector<int> a(n), b(n);

    for (int &i: a) cin >> i;    
    for (int &i: b) cin >> i;    


    int la=0, ra=0;
    int lb=0, rb=0;
    int curra = 0;
    int currb = 0;


    vector<array<int, 4>> bcktrck(n);

    for (int i = 0; i<n; i++) {
        bcktrck[i] = {la, ra, lb, rb};
        int nla=1e18, nra=-1e18;
        if (a[i] >= curra) {
            nla=min(nla,la+1);
            nra=max(nra,ra+1);
        }

        if (a[i] >= currb) {
            nla=min(nla,lb+1);
            nra=max(nra,rb+1);
        }


        int nlb=1e18, nrb=-1e18;
        if (b[i] >= curra) {
            nlb=min(nlb,la);
            nrb=max(nrb,ra);
        }

        if (b[i] >= currb) {
            nlb=min(nlb,lb);
            nrb=max(nrb,rb);
        }

        la=nla;
        ra=nra;
        lb=nlb;
        rb=nrb;
        curra = a[i];
        currb = b[i];
    }

    // bcktrck.push_back({la, ra, lb, rb});

    if (!(min(la, lb) <= n/2 && n/2 <= max(ra, rb))) {
        cout << -1 << "\n";
        return 0;
    }

    int currReq = n/2;
    bool currCol = 0;

    if (!(lb <= currReq && currReq <= rb)) currCol = 1;

    string res;

    for (int i = n-1; i>=0; i--) {
        if (currCol) res.push_back('A');
        else res.push_back('B');

        currReq -= currCol;

        int currVal = 0;

        if (currCol) currVal = a[i];
        if (!currCol) currVal = b[i];

        if ((i==0?1:(currVal >= a[i-1])) && bcktrck[i][0] <= currReq && currReq <= bcktrck[i][1]) {
            currCol = 1;
        }
        if ((i==0?1:(currVal >= b[i-1])) && bcktrck[i][2] <= currReq && currReq <= bcktrck[i][3]) {
            currCol = 0;
        }
    }

    reverse(res.begin(), res.end());

    cout << res << "\n";



    return 0;
}

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