Submission #471514

#	Time	Username	Problem	Language	Result	Execution time	Memory
471514		prvocislo	Building 4 (JOI20_building4)	C++17	100 / 100	319 ms	48212 KiB

building4

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5;
void chmin(int& a, const int& b) { a = min(a, b); }
void chmax(int& a, const int& b) { a = max(a, b); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	n *= 2;
	vector<vector<int> > l(2, vector<int>(n + 2, inf)), r(2, vector<int>(n + 2, -inf));
	vector<vector<int> > a(2, vector<int>(n + 2));
	a[0][0] = a[1][0] = -inf;
	for (int l = 0; l < 2; l++) for (int i = 0; i < n; i++) cin >> a[l][i + 1];
	a[0][n + 1] = a[1][n + 1] = inf;
	l[0][0] = l[1][0] = r[0][0] = r[1][0] = 0;
	for (int i = 1; i <= n + 1; i++)
	{
		for (int l1 = 0; l1 < 2; l1++) for (int l2 = 0; l2 < 2; l2++) if (a[l1][i - 1] <= a[l2][i] && l[l1][i - 1] != inf)
		{
			chmin(l[l2][i], l[l1][i - 1]);
			chmax(r[l2][i], r[l1][i - 1]);
		}
		l[1][i]++;
		r[1][i]++;
	}
	int pos = 0, b = n / 2;
	string ans;
	for (int i = n; i > 0; i--)
	{
		if (l[0][i] <= b && b <= r[0][i] && a[0][i] <= a[pos][i + 1])
		{
			ans.push_back('A');
			pos = 0;
		}
		else if (l[1][i] <= b && b <= r[1][i] && a[1][i] <= a[pos][i + 1])
		{
			ans.push_back('B');
			pos = 1;
			b--;
		}
		else
		{
			cout << "-1\n";
			return 0;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans << "\n";
	return 0;
}

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