Submission #1206335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206335		VMaksimoski008	Building 4 (JOI20_building4)	C++20	100 / 100	642 ms	119828 KiB

building4

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

signed main() {
    int n; cin >> n;
    vector<array<int, 2> > a(2*n+1);
    for(int i=1; i<=2*n; i++) cin >> a[i][0];
    for(int i=1; i<=2*n; i++) cin >> a[i][1];

    vector<vector<int> > dpL(2*n+1, vector<int>(2, 1e9));
    vector<vector<int> > dpR(2*n+1, vector<int>(2, -1e9));
    
    dpL[1] = { 0, 1 };
    dpR[1] = { 0, 1 };
    for(int i=2; i<=2*n; i++) {
        for(int j=0; j<2; j++) {
            for(int k=0; k<2; k++) {
                if(a[i][j] >= a[i-1][k]) {
                    dpL[i][j] = min(dpL[i][j], dpL[i-1][k] + j);
                    dpR[i][j] = max(dpR[i][j], dpR[i-1][k] + j);
                }
            }
        }
    }

    int p=-1;
    for(int i=0; i<2; i++)
        if(dpL[2*n][i] <= n && n <= dpR[2*n][i]) p = i;

    if(p == -1) {
        cout << -1 << endl;
        return 0;
    }

    string ans(2*n+1, 'A');
    if(p) ans[2*n] = 'B';

    int l=n-p, pos=2*n-1, last = a[2*n][p];
    for(; pos; pos--) {
        if(dpL[pos][0] <= l && l <= dpR[pos][0] && a[pos][0] <= last) {
            last = a[pos][0];
        } else if(dpL[pos][1] <= l && l <= dpR[pos][1] && a[pos][1] <= last) {
            ans[pos]++;
            last = a[pos][1];
            l--;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }

    for(int i=1; i<=2*n; i++) cout << ans[i];
}

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