Submission #859802

#	Time	Username	Problem	Language	Result	Execution time	Memory
859802		serifefedartar	Building 4 (JOI20_building4)	C++17	100 / 100	194 ms	45520 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];
int dp[MAXN][2][2];
vector<char> ans;

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][0] = 2*N+2, dp[i][0][1] = 0;
		dp[i][1][0] = 2*N+2, dp[i][1][1] = 0;
	}
	dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = 0;

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

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

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

	if (last == 0)
		ans.push_back('A');
	else
		ans.push_back('B');

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

		now = now - (last == 0);
		if (last == 0)
			ans.push_back('A');
		else
			ans.push_back('B');
	}

	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i];
	cout << "\n";
}

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