Submission #946750

#	Time	Username	Problem	Language	Result	Execution time	Memory
946750		LOLOLO	Building 4 (JOI20_building4)	C++17	100 / 100	210 ms	45484 KiB

building4

#include <bits/stdc++.h>
typedef long long ll;

#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)

using namespace std;
const int N = 1e6 + 100;
int A[N][2], mx[N][2], mi[N][2];
int c[2] = {-1, 1};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int sz = n * 2;

    for (int i = 1; i <= sz; i++)
        cin >> A[i][0];

    for (int i = 1; i <= sz; i++)
        cin >> A[i][1];

    for (int i = 1; i <= sz; i++) {
        mx[i][0] = mx[i][1] = -1e9;
        mi[i][0] = mi[i][1] = 1e9;
    }

    mi[sz][0] = mx[sz][0] = -1;
    mi[sz][1] = mx[sz][1] = 1;

    for (int i = sz - 1; i >= 1; i--) {      
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                if (A[i][j] <= A[i + 1][k]) {
                    mx[i][j] = max(mx[i][j], mx[i + 1][k] + c[j]);
                    mi[i][j] = min(mi[i][j], mi[i + 1][k] + c[j]);
                }
            }
        }
    }

    int x = 1, y = 0, all = 0;
    string ans;
    if (mi[x][y] > 0 || mx[x][y] < 0) {
        y = 1;
    }

    if (mi[x][y] > 0 || mx[x][y] < 0) {
        cout << -1 << '\n';
        return 0;
    }

    while (x <= sz) {
        if (y == 0) {
            ans += "A";
            all--;
        } else {
            ans += "B";
            all++;
        }

        if (x == sz)
            break;

        int t = 1;
        for (int k = 0; k < 2; k++) {
            if (A[x][y] <= A[x + 1][k]) {
                if (mi[x + 1][k] + all <= 0 && mx[x + 1][k] + all >= 0) {
                    t = k;
                    break;
                }
            }
        }
        x++;
        y = t;
    }

    cout << ans << '\n';
}

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