Submission #528867

#	Time	Username	Problem	Language	Result	Execution time	Memory
528867		Drew_	건물 4 (JOI20_building4)	C++17	100 / 100	294 ms	75624 KiB

building4

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 1e6 + 69;

int n;
int a[MAX], b[MAX];
ii dp[MAX][2];

ii merge(ii p, ii q)
{
	if (q == mp(1, 0)) return p;
	if (p == mp(1, 0)) return q;
	return {min(p.f1, q.f1), max(p.s2, q.s2)};
}

void rc(int i, int ty, int rem)
{
	if (i == 0) return;
	if (dp[i-1][0].f1 <= rem && rem <= dp[i-1][0].s2 && a[i-1] <= (ty ? b[i] : a[i])) rc(i-1, 0, rem);
	else rc(i-1, 1, rem - 1); 
		
	cout << (ty ? 'B' : 'A');
}

int main()
{
	fastio;

	cin >> n;
	for (int i = 1; i <= 2*n; ++i) 
		cin >> a[i];
	for (int i = 1; i <= 2*n; ++i)
		cin >> b[i];

	dp[1][0] = {0, 0};
	dp[1][1] = {1, 1};

	for (int i = 2; i <= 2*n; ++i)
	{
		{
			dp[i][0] = {1, 0};
			if (a[i-1] <= a[i]) dp[i][0] = merge(dp[i][0], dp[i-1][0]);
			if (b[i-1] <= a[i]) dp[i][0] = merge(dp[i][0], dp[i-1][1]);
		}
		{
			dp[i][1] = {1, 0};
			if (a[i-1] <= b[i]) dp[i][1] = merge(dp[i][1], dp[i-1][0]);
			if (b[i-1] <= b[i]) dp[i][1] = merge(dp[i][1], dp[i-1][1]);
			
			if (dp[i][1] != mp(1, 0))
				dp[i][1].f1++, dp[i][1].s2++;
		}
	}

	if (dp[2*n][0].f1 <= n && n <= dp[2*n][0].s2) rc(2*n, 0, n);
	else if (dp[2*n][1].f1 <= n && n <= dp[2*n][1].s2) rc(2*n, 1, n-1);
	else cout << -1;
	cout << '\n';

	return 0;
}

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