Submission #936242

#	Time	Username	Problem	Language	Result	Execution time	Memory
936242		Pring	Building 4 (JOI20_building4)	C++17	100 / 100	186 ms	44340 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 1000005;
int n, N, a[MXN], b[MXN];
int p[MXN];
string s, t, ans;
bitset<MXN> big, sml;
vector<pii> tanya;
vector<int> v;

void INIT() {
    ans = string(N, '-');
    s = string(N, 'A');
    t = string(N, 'B');
    FOR(i, 0, N) {
        if (a[i] > b[i]) {
            swap(a[i], b[i]);
            swap(s[i], t[i]);
        }
    }
}

bool DIE() {
    return (big & sml).any();
}

bool GET_NUM() {
    FOR(i, 0, N - 1) {
        int ls = a[i], lb = b[i], rs = a[i + 1], rb = b[i + 1];
        int val = (ls <= rs) + (ls <= rb) + (lb <= rs) + (lb <= rb);
        p[i] = val;
        if (val == 0) return false;
        if (val == 1) {
            sml[i] = true;
            big[i + 1] = true;
        }
        if (val == 2) {
            if (ls <= rs) {
                sml[i] = true;
            } else {
                big[i + 1] = true;
            }
        }
    }
    return true;
}

bool GET_3() {
    for (int i = 0, j = 0; i < N - 1; i = j) {
        while (j < N - 1 && (p[i] == 3) == (p[j] == 3)) j++;
        if (p[i] != 3) continue;
        int l = i, r = j;
        if (big[l] && sml[r]) return false;
        if (sml[r]) {
            FOR(k, l, r + 1) {
                sml[k] = true;
            }
            continue;
        }
        if (!big[l]) tanya.push_back(mp(l, r + 1));
        FOR(k, l, r + 1) {
            big[k] = true;
        }
    }
    return true;
}

void FREE() {
    FOR(i, 0, N) if (!big[i] && !sml[i]) {
        big[i] = true;
        tanya.push_back(mp(i, i + 1));
    }
}

bool SELECT() {
    int val = 0;
    FOR(i, 0, N) {
        if (sml[i]) val += (s[i] == 'A' ? 1 : -1);
        else val += (t[i] == 'A' ? 1 : -1);
        // cout << (sml[i] ? s[i] : t[i]);
    }
    // cout << endl;
    // cout << val << endl;
    // for (auto &[l, r] : tanya) cout << '<' << l << ' ' << r << "> ";
    // cout << endl;
    for (auto &[l, r] : tanya) {
        int now = val, pre = l;
        FOR(i, l, r) {
            now += (t[i] == 'A' ? -2 : 2);
            if (abs(now) < abs(val)) {
                // debug(i, now);
                FOR(j, pre, i + 1) {
                    sml[j] = true;
                    big[j] = false;
                }
                val = now;
                pre = i + 1;
            }
        }
    }
    return val == 0;
}

string miku() {
    cin >> n;
    N = n * 2;
    FOR(i, 0, N) cin >> a[i];
    FOR(i, 0, N) cin >> b[i];
    INIT();
    if (!GET_NUM()) return "-1";
    // FOR(i, 0, N - 1) cout << p[i] << ' ';
    // cout << endl;
    if (DIE()) return "-1";
    if (!GET_3()) return "-1";
    FREE();
    if (!SELECT()) return "-1";
    FOR(i, 0, N) ans[i] = (sml[i] ? s[i] : t[i]);
    return ans;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    cout << miku() << '\n';
    return 0;
}

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