Submission #543002

#	Time	Username	Problem	Language	Result	Execution time	Memory
543002		MarcosPauloEvers	Building 4 (JOI20_building4)	C++17	100 / 100	318 ms	45504 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int arr[2][MAXN], dp[2][MAXN][2];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i = 0; i < (n<<1); i++) cin >> arr[0][i];
	for(int i = 0; i < (n<<1); i++) cin >> arr[1][i];

	for(int i = 0; i < (n<<1) - 1; i++)
	{
		bool flag = false;
		for(auto& k: {0, 1})
			if(arr[k][i] <= arr[k][i+1] ||
				arr[k][i] <= arr[k^1][i+1])
				flag = true;

		if(!flag)
			return cout << -1 << "\n", 0;
	}
	
	for(auto& k: {0, 1})
		dp[k][n << 1][0] = dp[k][n << 1][1] = 0;
	for(int i = (n<<1) - 1; i >= 1; i--)
		for(int f: {0, 1})
		{
			dp[0][i][f] = arr[1][i] >= arr[f][i-1] ? dp[0][i+1][1] : INF;

			if(arr[0][i] >= arr[f][i - 1]) 
				dp[0][i][f] = min(dp[0][i][f], 1 + dp[0][i+1][0]);
		}

	for(int i = (n<<1) - 1; i >= 1; i--)
		for(int f: {0, 1})
		{
			dp[1][i][f] = arr[1][i] >= arr[f][i-1] ? dp[1][i+1][1] : -INF;

			if(arr[0][i] >= arr[f][i - 1] && dp[1][i+1][0] != -INF) 
				dp[1][i][f] = max(dp[1][i][f], dp[1][i+1][0]+1);
		}
	
	string ans = "";
	int cnt = n, last = 0;
	for(int i = 0; i < (n<<1); i++)
	{
		if(arr[0][i] >= last &&
			dp[0][i+1][0] <= cnt-1 &&
			dp[1][i+1][0] >= cnt-1 && cnt > 0)
			ans += "A", last = arr[0][i], cnt--;
		else if(dp[0][i+1][1] <= cnt &&
				dp[1][i+1][1] >= cnt && arr[1][i] >= last)
			ans += "B", last = arr[1][i];
		else
			return cout << -1 << "\n", 0;
	}
	cout << ans << "\n";
	return 0;
}

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