Submission #1201693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201693		g4yuhg	Building 4 (JOI20_building4)	C++20	100 / 100	221 ms	118848 KiB

building4

#include<bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define inf 1e9
#define N 1000006
using namespace std;
ll n, m;
ll a[N], b[N], dd[N];
ll f[4002][2002][2];
ll dp(ll i, ll j, ll tt) {
	if (i > n * 2) {
		if (j == n) {
			return 1;
		}
		return 0;
	}
	if (f[i][j][tt] != -1) {
		return f[i][j][tt];
	}
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	ll res = 0;
	if (a[i] >= last && j <= n) {
		res = max(res, dp(i + 1, j + 1, 0));
	}
	if (b[i] >= last) {
		res = max(res, dp(i + 1, j, 1) );
	}
	f[i][j][tt] = res;
	return res;
}
pii f2[N][2];
pii merge(pii a, pii b, ll u) {
	return {min(a.fi, b.fi + u), max(a.se, b.se + u)};
}
pii dp2(ll i, ll tt) {
	if (i > n + n) {
		return {0, 0};
	}
	if (f2[i][tt].fi != -1) {
		return f2[i][tt];
	}
	pii res = {inf, -inf};
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	if (a[i] >= last) {
		res = merge(res, dp2(i + 1, 0), 1);
	}
	if (b[i] >= last) {
		res = merge(res, dp2(i + 1, 1), 0);
	}
	f2[i][tt] = res;
	return res;
}
void trace(ll i, ll j, ll tt) {
	if (i > n * 2) {
		return;
	}
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	if (a[i] >= last && j <= n) {
		//res = max(res, dp(i + 1, j + 1, 0));
		if (dp(i + 1, j + 1, 0) == 1) {
			dd[i] = 1;
			trace(i + 1, j + 1, 0);
			return;
		}
	}
	if (b[i] >= last) {
		//res = max(res, dp(i + 1, j, 1) );
		if (dp(i + 1, j, 1) == 1) {
			trace(i + 1, j, 1);
			return;
		}
	}
}
void sub1() {
	memset(f, -1, sizeof(f));
	ll x = dp(1, 0, 0);
	if (x == 0) {
		cout << -1;
		return;
	}
	trace(1, 0, 0);
	for (int i = 1; i <= n + n; i ++) {
		if (dd[i]) {
			cout << "A";
		}
		else {
			cout << "B";
		}
	}
}
void trace2(ll i, ll tt, ll used) {
	if (i > n + n) return;
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	if (a[i] >= last) {
		pii res = dp2(i + 1, 0);
		if (res.fi + 1 <= used && used <= res.se + 1) {
			dd[i] = 1;
			trace2(i + 1, 0, used - 1);
			return;
		}
	}
	if (b[i] >= last) {
		pii res = dp2(i + 1, 1);
		if (res.fi <= used && used <= res.se) {
			dd[i] = 0;
			trace2(i + 1, 1, used);
			return;
		}
	}
}
void sub2() {
	for (int i = 0; i <= n + n; i ++) {
		f2[i][0].fi = -1;
		f2[i][1].fi = -1;
	}
	pii res = dp2(1, 0);
	ll used = n;
	if (!(res.fi <= used && used <= res.se)) {
		cout << -1;
	}
	else {
		trace2(1, 0, used);
		for (int i = 1; i <= n + n; i ++) {
			if (dd[i] == 1) {
				cout << "A";
			}
			else {
				cout << "B";
			}
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n + n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n + n; i ++) {
		cin >> b[i];
	}
	sub2();
	return 0;
}

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