oj.uz

Submission #936693

# Submission time Handle Problem Language Result Execution time Memory
936693 2024-03-02T14:26:05 Z velislavgarkov Building 4 (JOI20_building4) C++14
0 / 100
 4 ms 10588 KB 
#include <iostream>
using namespace std;
const int MAXN=1e6+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++) {
        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);
        }
    }
    int cnta, cntb;
    cnta=cntb=n;
    for (int i=2*n-1;i>=0;i--) {
        if (cnta>0 && (i==2*n-1 || 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 && (i==2*n-1 || 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 2 ms 8660 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 2 ms 8660 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -