Submission #1000667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000667		42kangaroo	Building 4 (JOI20_building4)	C++17	100 / 100	194 ms	47236 KiB

building4

//
// Created by 42kangaroo on 18/06/2024.
//
#include "bits/stdc++.h"

using namespace std;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	array<vector<int>, 2> a;
	a.fill(vector<int>(2 * n));
	array<vector<pair<int, int>>, 2> dp;
	dp.fill(vector<pair<int, int>>(2 * n, {1e9, 0}));
	for (int i = 0; i < 2 * n; ++i) {
		cin >> a[0][i];
	}
	for (int i = 0; i < 2 * n; ++i) {
		cin >> a[1][i];
	}
	dp[0][0] = {0, 0};
	dp[1][0] = {1, 1};
	for (int i = 1; i < 2 * n; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				if (a[j][i - 1] <= a[k][i]) {
					dp[k][i] = {min(dp[k][i].first, dp[j][i - 1].first + k),
					            max(dp[k][i].second, dp[j][i - 1].second + k)};
				}
			}
		}
	}
	string ans;
	pair<int, int> act = {-1, -1};
	int nu = 0;
	for (int j = 0; j < 2; ++j) {
		if (dp[j].back().first <= n && n <= dp[j].back().second) {
			act = {j, 2 * n - 1};
			nu += j;
			ans += (j ? "B" : "A");
			break;
		}
	}
	if (act.first == -1) {
		cout << -1;
		return 0;
	}
	while (ans.size() < 2 * n) {
		for (int j = 0; j < 2; ++j) {
			if (a[j][act.second - 1] <= a[act.first][act.second] && dp[j][act.second - 1].first <= n - nu && n - nu <= dp[j][act.second - 1].second) {
				nu += j;
				act = {j, act.second - 1};
				ans += (j ? "B" : "A");
				break;
			}
		}
	}
	std::reverse(ans.begin(), ans.end());
	cout << ans;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:50:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  while (ans.size() < 2 * n) {
      |         ~~~~~~~~~~~^~~~~~~

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