Submission #936695

#	Time	Username	Problem	Language	Result	Execution time	Memory
936695		velislavgarkov	Building 4 (JOI20_building4)	C++14	100 / 100	206 ms	49236 KiB

building4

#include <iostream>
using namespace std;
const int MAXN=1e6+10;
const int INF=1e9+10;
int a[MAXN], b[MAXN], arr[MAXN];
int dpa[MAXN][2], dpb[MAXN][2];
char ans[MAXN];
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i=0;i<2*n;i++) cin >> a[i];
    for (int i=0;i<2*n;i++) cin >> b[i];
    dpa[0][0]=1;
    dpb[0][1]=1;
    for (int i=1;i<2*n;i++) {
        dpa[i][0]=dpb[i][0]=-INF;
        dpa[i][1]=dpb[i][1]=-INF;
        if (a[i]>=a[i-1]) {
            dpa[i][0]=max(dpa[i][0],dpa[i-1][0]+1);
            dpb[i][0]=max(dpb[i][0],dpb[i-1][0]);
        }
        if (a[i]>=b[i-1]) {
            dpa[i][0]=max(dpa[i][0],dpa[i-1][1]+1);
            dpb[i][0]=max(dpb[i][0],dpb[i-1][1]);
        }
        if (b[i]>=a[i-1]) {
            dpa[i][1]=max(dpa[i][1],dpa[i-1][0]);
            dpb[i][1]=max(dpb[i][1],dpb[i-1][0]+1);
        }
        if (b[i]>=b[i-1]) {
            dpa[i][1]=max(dpa[i][1],dpa[i-1][1]);
            dpb[i][1]=max(dpb[i][1],dpb[i-1][1]+1);
        }
    }
    if (max(dpa[2*n-1][0],dpa[2*n-1][1])<n || max(dpb[2*n-1][0],dpb[2*n-1][1])<n) {
        cout << -1 << endl;
        return 0;
    }
    int cnta, cntb;
    cnta=cntb=n;
    arr[2*n]=INF;
    for (int i=2*n-1;i>=0;i--) {
        if (cnta>0 && a[i]<=arr[i+1] && dpa[i][0]>=cnta && dpb[i][0]>=cntb) {
            cnta--;
            arr[i]=a[i];
            ans[i]='A';
            continue;
        }
        if (cntb>0 && b[i]<=arr[i+1] && dpa[i][1]>=cnta && dpb[i][1]>=cntb) {
            cntb--;
            arr[i]=b[i];
            ans[i]='B';
            continue;
        }
        cout << -1 << endl;
        return 0;
    }
    for (int i=0;i<2*n;i++) cout << ans[i];
    cout << endl;
    return 0;
}

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