Submission #1150318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150318		dosts	Building 4 (JOI20_building4)	C++20	100 / 100	168 ms	49436 KiB

building4

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 2e6+1,MOD = (1LL<<61)-1,B = 23;

void solve() { 
    int n;
    cin >> n;
    n*=2;
    int v[n+1][2]{};
    for (int i=1;i<=n;i++) cin >> v[i][0];
    for (int i=1;i<=n;i++) cin >> v[i][1];
    pii dp[n+1][2];
    for (int i=0;i<=n;i++) for (int j = 0;j<2;j++) dp[i][j] = {inf,-inf};
    dp[0][0] = dp[0][1] = {0,0};
    for (int i=0;i<n;i++) {
        for (int j = 0;j<2;j++) {
            int prv = v[i][j];
            if (v[i+1][0] >= prv) {
                dp[i+1][0].ff = min(dp[i+1][0].ff,dp[i][j].ff+1);
                dp[i+1][0].ss = max(dp[i+1][0].ss,dp[i][j].ss+1);
            }
            if (v[i+1][1] >= prv) {
                dp[i+1][1].ff = min(dp[i+1][1].ff,dp[i][j].ff);
                dp[i+1][1].ss = max(dp[i+1][1].ss,dp[i][j].ss);
            }
        }
    }
    string ans;
    if (dp[n][0].ff <= n/2 && dp[n][0].ss >= n/2) {
        int ptr = n;
        int cur = 0;
        int usea = 0;
        while (ptr >= 1) {
            if (!cur) ans+='A';
            else ans+='B';
            if (ptr > 1) {
                if (usea+dp[ptr-1][0].ff+1 <= n/2 && usea+dp[ptr-1][0].ss+1 >= n/2 && v[ptr-1][0] <= v[ptr][cur]) {
                    usea++;
                    ptr--;
                    cur = 0;
                    continue;
                }
                else {
                    ptr--;
                    cur = 1;
                    continue;  
                }
            }
            else break;
        }
        reverse(all(ans));
        cout << ans << '\n';
        return;
    }
    if (dp[n][1].ff <= n/2 && dp[n][1].ss >= n/2) {
        int ptr = n;
        int cur = 1;
        int usea = 0;
        while (ptr >= 1) {
            if (!cur) ans+='A';
            else ans+='B';
            if (ptr > 1) {
                if (usea+dp[ptr-1][0].ff <= n/2 && usea+dp[ptr-1][0].ss >= n/2 && v[ptr-1][0] <= v[ptr][cur]) {
                    usea++;
                    ptr--;
                    cur = 0;
                    continue;
                }
                else {
                    ptr--;
                    cur = 1;
                    continue;  
                }
            }
            else break;
        }
        reverse(all(ans));
        cout << ans << '\n';
        return;
    }
    cout << -1 << '\n';
    return;
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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