Submission #1068986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068986		_8_8_	Building 4 (JOI20_building4)	C++17	100 / 100	189 ms	45520 KiB

building4

#include <bits/stdc++.h>

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

int n,a[N][2];
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]);
                }
            }
        }
    }
    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';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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