Submission #523241

#	Time	Username	Problem	Language	Result	Execution time	Memory
523241		CPSC	Building 4 (JOI20_building4)	C++14	100 / 100	854 ms	44912 KiB

building4

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 1e6 + 5,inf = 1e9;
int le[2][N],ri[2][N], a[2][N],n,id,lst,cnt,ans[N];
main() {
    cin>>n;
    for (int i = 1; i <= 2*n; i++) {
        cin>>a[0][i];
        le[0][i] = inf; le[1][i] = inf;
        ri[0][i] = 0; ri[1][i] = 0;
    }
    for (int i = 1; i <= 2*n; i++) {
        cin>>a[1][i];
    }
    for (int i = 1; i <= 2*n; i++) {
        for (int j = 0; j <= 1; j++) {
            if (j == 0) {
               if (a[0][i - 1] <= a[0][i]) {
                   le[0][i] = min(le[0][i - 1] + 1, le[0][i]);
                   ri[0][i] = max(ri[0][i - 1] + 1, ri[0][i]);
               }
               if (a[1][i - 1] <= a[0][i]) {
                   le[0][i] = min(le[1][i - 1] + 1, le[0][i]);
                   ri[0][i] = max(ri[1][i - 1] + 1, ri[0][i]);
               }
                continue;
            }
            if (a[0][i - 1] <= a[1][i]) {
                le[1][i] = min(le[0][i - 1], le[1][i]);
                ri[1][i] = max(ri[0][i - 1], ri[1][i]);
            }
            if (a[1][i - 1] <= a[1][i]) {
                le[1][i] = min(le[1][i - 1], le[1][i]);
                ri[1][i] = max(ri[1][i - 1], ri[1][i]);
            }
        }
    }
    id = -1;
    if (n >= le[0][2*n] && n <= ri[0][2*n]) {
        id = 0;
    } else
    if (n >= le[1][2*n] && n <= ri[1][2*n]) {
        id = 1;
    }
    if (id == -1)  {
        cout<<-1<<endl;
        return 0;
    }
    cnt = 0;
    lst = 2 * n;
    while (lst >= 1) {
        if (id == 0) cnt++,ans[lst] = 1;
        else ans[lst] = 2;
        if (lst == 1) break;
        if (le[0][lst - 1] + cnt <= n && ri[0][lst - 1] + cnt >= n && a[0][lst - 1] <= a[id][lst]) {
            id = 0;
            lst--;
            continue;
        }
        id = 1;
        lst--;
    }
    for (int i = 1; i <= 2 * n; i++) {
        cout<<(ans[i] == 1 ? "A" : "B");
    }
}

Compilation message (stderr)

building4.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main() {
      | ^~~~

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