Submission #988794

#	Time	Username	Problem	Language	Result	Execution time	Memory
988794		_callmelucian	Building 4 (JOI20_building4)	C++14	100 / 100	520 ms	77004 KiB

building4

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e6 + 6;
int a[2][mn], dpLow[2][mn], dpHigh[2][mn];
vector<char> ans;

bool ok (int cur, int i, int need) {
    return dpLow[cur][i] <= need && need <= dpHigh[cur][i];
}

void trace (int cur, int i, int need) {
    if (i == 1) return ans.push_back(cur + 'A'), void();
    for (int pre = 0; pre < 2; pre++) {
        if (a[pre][i - 1] <= a[cur][i] && ok(pre, i - 1, need - cur)) {
            trace(pre, i - 1, need - cur);
            return ans.push_back(cur + 'A'), void();
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    n <<= 1;

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= n; i++) cin >> a[j][i];

    for (int i = 1; i <= n; i++) {
        for (int cur = 0; cur < 2; cur++) {
            dpLow[cur][i] = INT_MAX, dpHigh[cur][i] = INT_MIN;
            for (int pre = 0; pre < 2; pre++) {
                if (a[pre][i - 1] > a[cur][i]) continue;
                if (dpLow[pre][i - 1] != INT_MAX)
                    dpLow[cur][i] = min(dpLow[cur][i], dpLow[pre][i - 1] + cur);
                if (dpHigh[pre][i - 1] != INT_MAX)
                    dpHigh[cur][i] = max(dpHigh[cur][i], dpHigh[pre][i - 1] + cur);
            }
        }
    }

    if (!ok(0, n, n / 2) && !ok(1, n, n / 2))
        return cout << -1, 0;
    if (ok(0, n, n / 2)) trace(0, n, n / 2);
    else trace(1, n, n / 2);

    for (char c : ans) cout << c;

    return 0;
}

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