Submission #859795

#	Time	Username	Problem	Language	Result	Execution time	Memory
859795		serifefedartar	Building 4 (JOI20_building4)	C++17	11 / 100	2056 ms	24600 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 22; 
const ll MAXN = 1e6 + 5;

int A[MAXN], B[MAXN];
pair<int,int> dp[MAXN][2];

int main() {
	fast
	int N;
	cin >> N;

	for (int i = 1; i <= 2*N; i++)
		cin >> A[i];
	for (int i = 1; i <= 2*N; i++)
		cin >> B[i];

	for (int i = 0; i < MAXN; i++)
		dp[i][0] = dp[i][1] = {2*N+2, 0};
	dp[0][0] = dp[0][1] = {0, 0};

	for (int i = 1; i <= 2*N; i++) {
		if (A[i-1] <= A[i])
			dp[i][0] = {min(dp[i][0].f, dp[i-1][0].f + 1), max(dp[i][0].s, dp[i-1][0].s + 1)};
		if (A[i-1] <= B[i])
			dp[i][1] = {min(dp[i][1].f, dp[i-1][0].f), max(dp[i][1].s, dp[i-1][0].s)};
		if (B[i-1] <= A[i])
			dp[i][0] = {min(dp[i][0].f, dp[i-1][1].f + 1), max(dp[i][0].s, dp[i-1][1].s + 1)};
		if (B[i-1] <= B[i])
			dp[i][1] = {min(dp[i][1].f, dp[i-1][1].f), max(dp[i][1].s, dp[i-1][1].s)};
	}

	int last = -1;
	if (dp[2*N][0].f <= N && N <= dp[2*N][0].s)
		last = 0;
	else if (dp[2*N][1].f <= N && N <= dp[2*N][1].s)
		last = 1;

	if (last == -1) {
		cout << "-1\n";
		return 0;
	}

	string ans;
	ans = (last == 0 ? "A" : "B") + ans;
	int now = N - (last == 0);
	for (int i = 2*N - 1; i >= 1; i--) {
		if (dp[i][0].f <= now && now <= dp[i][0].s && A[i] <= (last == 0 ? A[i+1] : B[i+1]))
			last = 0;
		else if (dp[i][1].f <= now && now <= dp[i][1].s)
			last = 1;

		now = now - (last == 0);
		ans = (last == 0 ? "A" : "B") + ans;
	}

	cout << ans << "\n";
}

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