Submission #1068984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068984		_8_8_	Building 4 (JOI20_building4)	C++17	0 / 100	1 ms	604 KiB

building4

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 100 + 12, MOD = (int)1e9 + 7;

int n,a[N][2];
int dp[N][2][N];
int mx[N][2],mn[N][2];
bool in(int l,int r,int x) {
    return (l <= x && x <= r);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n + n; i++) {
        cin >> a[i][1];
    }
    for(int i = 1; i <= n + n; i++) {
        cin >> a[i][0];
    }
    for(int i = 1; i <= n + n; i++) {
        for(int k = 0;k < 2;k++) {
            mn[i][k] = 1e9;
            mx[i][k] = -1e9;
            for(int t = 0;t < 2;t++) {
                if(a[i][k] >= a[i - 1][t]) {
                    mx[i][k] = max(mx[i - 1][t] + k,mx[i][k]);
                    mn[i][k] = min(mn[i][k],k + mn[i - 1][t]);
                    // cout << i << ' ' << k << ' ' << t << ' ' <<mx[i - 1][t] + k << ' ' << mn[i - 1][t] + k << '\n';
                }
            }
        }
        // cout << i << ' ' << mn[i][1] << ' ' << mx[i][1] << ' ' << mn[i][0] << ' ' << mx[i][0] << '\n';
    }
    if(!in(mn[n + n][0],mx[n + n][0],n) && !in(mn[n + n][1],mx[n + n][1],n)) {
        cout << -1 << '\n';
        return;
    }
    int cur = n,lst = 1e9 + 1;
    vector<char> res;
    for(int i = n + n;i >= 1;i--) {
        if(cur && a[i][1] <= lst && in(mn[i][1],mx[i][1],cur)) {
            cur--;
            res.push_back('A');
            lst = a[i][1];
        } else {
            lst = a[i][0];
            res.push_back('B');
        }
    }
    reverse(res.begin(),res.end());
    for(auto x:res) {
        cout << x;
    }
    cout << '\n';
    // dp[0][0][0] = dp[0][1][0] = 1;
    // for(int i = 1; i <= n + n; i++) {
    //     for(int j = 0; j <= i; j++) {
    //         for(int k = 0; k < 2; k++) {
    //             for(int t = 0; t < 2; t++) {
    //                 if(a[i][k] >= a[i - 1][t] && j - (!k) >= 0) {
    //                     dp[i][k][j] |= dp[i - 1][t][j - (!k)];
    //                 }
    //             }
    //         }
    //     }
    //     for(int j = 0;j <= i;j++) {
    //         cout << (dp[i][0][j]);
    //     }
    //     cout << '\n';
    //     for(int j = 0;j <= i;j++) {
    //         cout << (dp[i][1][j]);
    //     }
    //     cout << '\n';
    // }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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