Submission #414163

#	Time	Username	Problem	Language	Result	Execution time	Memory
414163		usachevd0	Building 4 (JOI20_building4)	C++14	100 / 100	288 ms	45332 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


const int INF32 = 1e9;
const int maxN = 1e6 + 6;
int n;
int A[maxN][2];
int mn[maxN][2], mx[maxN][2];

const char ch[] = "AB";

int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    n *= 2;
    for (int t = 0; t < 2; ++t)
        for (int i = 0; i < n; ++i)
            cin >> A[i][t];
    mn[0][0] = mx[0][0] = 0;
    mn[0][1] = mx[0][1] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            mn[i][j] = +INF32;
            mx[i][j] = -INF32;
            for (int t = 0; t < 2; ++t) {
                if (A[i - 1][t] <= A[i][j]) {
                    chkmin(mn[i][j], mn[i - 1][t] + j);
                    chkmax(mx[i][j], mx[i - 1][t] + j);
                }
            }
        }
    }
    for (int t = 0; t < 2; ++t) {
        if (mn[n - 1][t] <= n / 2 && n / 2 <= mx[n - 1][t]) {
            int need = n / 2;
            string res(n, '?');
            res[n - 1] = ch[t];
            for (int i = n - 1; i > 0; --i) {
                for (int j = 0; j < 2; ++j) {
                    if (A[i - 1][j] <= A[i][t] && mn[i - 1][j] + t <= need && need <= mx[i - 1][j] + t) {
                        need -= t;
                        t = j;
                        break;
                    }
                }
                res[i - 1] = ch[t];
            }
            cout << res << '\n';
            exit(0);
        }
    }
    cout << "-1\n";

    return 0;
}

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