Submission #1220001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220001		LIA	Building 4 (JOI20_building4)	C++17	100 / 100	191 ms	88532 KiB

building4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
ll n;
vll a,b;
int main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    a.resize(n*2), b.resize(n*2);
    loop(i,0,n*2) cin>>a[i];
    loop(i,0,n*2) cin>>b[i];
    vvpll dp(2*n, vpll(2,{inf, -inf}));
    dp[0][0] = {1,1};
    dp[0][1] = {0,0};
    loop(i,1,2*n) {
        ll aval = a[i], bval = b[i];
        dp[i][0] = {inf, -inf};
        dp[i][1] = {inf, -inf};
        ll L,R;
        if(dp[i-1][0].first <= dp[i-1][0].second && a[i-1] <= aval) {
            L = dp[i-1][0].first + 1;
            R = dp[i-1][0].second + 1;
            dp[i][0].first = min(dp[i][0].first, L);
            dp[i][0].second = max(dp[i][0].second, R);
        }
        if(dp[i-1][1].first <= dp[i-1][1].second && b[i-1] <= aval) {
            L = dp[i-1][1].first + 1;
            R = dp[i-1][1].second + 1;
            dp[i][0].first = min(dp[i][0].first, L);
            dp[i][0].second = max(dp[i][0].second, R);
        }
        if(dp[i-1][0].first <= dp[i-1][0].second && a[i-1] <= bval) {
            L = dp[i-1][0].first;
            R = dp[i-1][0].second;
            dp[i][1].first = min(dp[i][1].first, L);
            dp[i][1].second = max(dp[i][1].second, R);
        }
        if(dp[i-1][1].first <= dp[i-1][1].second && b[i-1] <= bval) {
            L = dp[i-1][1].first;
            R = dp[i-1][1].second;
            dp[i][1].first = min(dp[i][1].first, L);
            dp[i][1].second = max(dp[i][1].second, R);
        }
    }
    pll t0 = dp[2*n-1][0], t1 = dp[2*n-1][1];
    if(!(t0.first <= n && n <= t0.second) && !(t1.first <= n && n <= t1.second)) {
        cout<<-1;
        return 0;
    }
    int st = (t0.first <= n && n <= t0.second ? 0 : 1);
    ll k = n;
    string s(2*n,'?');
    loopr(i,2*n,0) {
        if(st==0) {
            s[i] = 'A';
            --k;
            if(i>0) {
                if(dp[i-1][0].first <= k && k <= dp[i-1][0].second && a[i-1] <= a[i]) st = 0;
                else st = 1;
            }
        } else {
            s[i] = 'B';
            if(i>0) {
                if(dp[i-1][0].first <= k && k <= dp[i-1][0].second && a[i-1] <= b[i]) st = 0;
                else st = 1;
            }
        }
    }
    cout<<s;
    return 0;
}

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