Submission #596817

#	Time	Username	Problem	Language	Result	Execution time	Memory
596817		penguinhacker	Building 4 (JOI20_building4)	C++17	100 / 100	281 ms	45388 KiB

building4

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

#define ll long long
#define ar array

const int mxN=5e5;
int n, a[2*mxN][2], dp[2*mxN][2][2]; // take a, b, max a, max b

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int j : {0, 1})
		for (int i=0; i<2*n; ++i)
			cin >> a[i][j];
	memset(dp, -1, sizeof(dp));
	dp[0][0][0]=1, dp[0][0][1]=0, dp[0][1][1]=1, dp[0][1][0]=0;
	for (int i=1; i<2*n; ++i) {
		for (int j : {0, 1}) {
			for (int k : {0, 1}) {
				if (a[i-1][k]<=a[i][j]&&dp[i-1][k][0]!=-1) {
					dp[i][j][0]=max(dp[i][j][0], dp[i-1][k][0]+(j==0));
					dp[i][j][1]=max(dp[i][j][1], dp[i-1][k][1]+(j==1));
				}
			}
		}
	}
	for (int x : {0, 1}) {
		if (dp[2*n-1][x][0]>=n&&dp[2*n-1][x][1]>=n) {
			string ans(2*n, 'A');
			int need[2]={n, n};
			for (int i=2*n-1, j=x; ~i; --i) {
				ans[i]='A'+j;
				--need[j];
				if (i) {
					bool ok=0;
					for (int k : {0, 1})
						if (a[i-1][k]<=a[i][j]&&dp[i-1][k][0]>=need[0]&&dp[i-1][k][1]>=need[1]) {
							j=k;
							ok=1;
							break;
						}
					assert(ok);
				}
			}
			cout << ans;
			return 0;
		}
	}
	cout << -1;
	return 0;
}

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