제출 #981778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981778		samek08	건물 4 (JOI20_building4)	C++14	100 / 100	193 ms	45360 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

struct Prz
{
	int l,p;
};

const int MAXN = 1e6+5, INF = 2e9+50;
const ull INF_L = (ull)1e19+500;

int n;
int A[2][MAXN];
Prz dp[2][MAXN];

void solve()
{
	cin >> n;
	rep(j,2) rep(i,n*2) cin >> A[j][i];

	dp[0][0] = {1,1}, dp[1][0] = {0,0};
	for(int i = 1; i < n*2; ++i)
	{
		dp[0][i] = {INF,-INF};
		if(A[0][i-1] <= A[0][i]) dp[0][i] = {min(dp[0][i].l,dp[0][i-1].l),max(dp[0][i].p,dp[0][i-1].p)};
		if(A[1][i-1] <= A[0][i]) dp[0][i] = {min(dp[0][i].l,dp[1][i-1].l),max(dp[0][i].p,dp[1][i-1].p)};
		dp[0][i] = {dp[0][i].l+1,dp[0][i].p+1};

		dp[1][i] = {INF,-INF};
		if(A[0][i-1] <= A[1][i]) dp[1][i] = {min(dp[1][i].l,dp[0][i-1].l),max(dp[1][i].p,dp[0][i-1].p)};
		if(A[1][i-1] <= A[1][i]) dp[1][i] = {min(dp[1][i].l,dp[1][i-1].l),max(dp[1][i].p,dp[1][i-1].p)};
	}

	int x = 2*n-1, y = 0, uz = n;
	if(dp[0][2*n-1].l <= n and dp[0][2*n-1].p >= n) y = 0;
	else if(dp[1][2*n-1].l <= n and dp[1][2*n-1].p >= n) y = 1;
	else
	{
		cout << "-1" << '\n';
		return;
	}

	string res;

	while(x >= 0)
	{
		if(y == 0) res.pb('A'), --uz;
		else res.pb('B');

		if(x == 0) break;
		if(dp[0][x-1].l <= uz and dp[0][x-1].p >= uz and A[0][x-1] <= A[y][x]) --x, y = 0;
		else --x, y = 1;
	}

	reverse(all(res)), cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    int T = 1;
   	//cin >> T;
    while(T--) solve();

    return 0;
}

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