Submission #528880

#	Time	Username	Problem	Language	Result	Execution time	Memory
528880		ajpiano	Building 4 (JOI20_building4)	C++17	11 / 100	609 ms	524292 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 1e5+5;

bitset<large/2> dp[large][2];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> a(2*n), b(2*n);
    for(int i = 0; i < 2*n; i++) cin >> a[i];
    for(int i = 0; i < 2*n; i++) cin >> b[i];
    dp[0][0][0] = 1;
    dp[0][1][1] = 1;
    for(int i = 1; i < 2*n; i++){
        if(a[i-1] <= a[i]) dp[i][0] = dp[i-1][0];
        if(b[i-1] <= b[i]) dp[i][1] = dp[i-1][1]<<1;
        if(b[i-1] <= a[i]) dp[i][0] |= dp[i-1][1];
        if(a[i-1] <= b[i]) dp[i][1] |= dp[i-1][0]<<1;
    }
    if(dp[2*n-1][0][n]|dp[2*n-1][1][n]){
        string ans = "";
        bool cur = 0;
        int num = n;
        if(dp[2*n-1][0][n]){
            ans += 'A';
            num = n;
            if(a[2*n-1] >= a[2*n-2] && dp[2*n-2][0][num]) cur = 0;
            else cur = 1;
        }else{
            ans += 'B';
            num = n-1;
            if(b[2*n-1] >= b[2*n-2] && dp[2*n-2][1][num]) cur = 1;
            else cur = 0;
        }
        for(int i = 2*n-2; i > 0; i--){
            if(cur == 0){
                ans += 'A';
                num = num;
                if(a[i] >= a[i-1] && dp[i-1][0][num]) cur = 0;
                else cur = 1;
            }else{
                ans += 'B';
                num = num-1;
                if(b[i] >= b[i-1] && dp[i-1][1][num]) cur = 1;
                else cur = 0;
            }
        }
        if(cur) ans += 'B';
        else ans += 'A';
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }else cout << "-1\n";
    return 0;
}

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