제출 #536122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536122		ngpin04	건물 4 (JOI20_building4)	C++14	100 / 100	348 ms	33296 KiB

building4

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

pair <int, int> dp[N][2];

int a[N][2];
int n;

string ans;

void trace(int i, int cur, int lef) {
	ans += ('A' + cur);
	if (i == 1) {
		reverse(ALL(ans));
		return;
	}

	lef -= !cur;

	for (int pre = 0; pre < 2; pre++) if (a[i - 1][pre] <= a[i][cur]) {
		int l = dp[i - 1][pre].fi;
		int r = dp[i - 1][pre].se;
		if (l <= lef && lef <= r) {
			trace(i - 1, pre, lef);
			return;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n;
	for (int j = 0; j < 2; j++)
	for (int i = 1; i <= 2 * n; i++)
		cin >> a[i][j];

	dp[0][1] = mp(0, 0);
	dp[0][0] = mp(0, 0);

	for (int i = 1; i <= 2 * n; i++)
	for (int j = 0; j < 2; j++)
		dp[i][j] = mp(-1, -1);

	for (int i = 0; i < 2 * n; i++)
	for (int j = 0; j < 2; j++) {
		int l = dp[i][j].fi;
		int r = dp[i][j].se;

		if (l < 0)
			continue;
		for (int k = 0; k < 2; k++) if (a[i][j] <= a[i + 1][k]) {
			int u = dp[i + 1][k].fi;
			int v = dp[i + 1][k].se;
			if (k == 0) {
				l++;
				r++;
			}

			if (u < 0) {
				dp[i + 1][k] = mp(l, r);
			} else {
				dp[i + 1][k] = mp(min(l, u), max(r, v));
			}

			if (k == 0) {
				l--;
				r--;
			}
		}
	}

	ans = "-1";
	for (int i = 0; i < 2; i++) {
		if (dp[2 * n][i].fi <= n && n <= dp[2 * n][i].se) {
			ans.clear();
			trace(2 * n, i, n);
			break;
		}
	}
	cout << ans;
	return 0;
}

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