Submission #1258782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258782		namhh	Building 4 (JOI20_building4)	C++20	100 / 100	145 ms	26048 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+5;
int n,a[N],b[N],dp1[N][2],dp2[N][2];
void trace(int x, int y, int rem){
	string s;
	if(y == 0) s += 'A';
	else s += 'B';
	while(x > 1){
		if(y == 0){
			if(a[x] >= a[x-1] && dp1[x-1][0] >= rem && dp2[x-1][0] <= rem){
				s += 'A';
				y = 0;
				rem--;
			}
			else{
				s += 'B';
				y = 1;
			}  
		}
		else{
			if(b[x] >= a[x-1] && dp1[x-1][0] >= rem && dp2[x-1][0] <= rem){
				s += 'A';
				y = 0;
				rem--;
			}
			else{
				s += 'B';
				y = 1;
			}  
		}
		x--;
	}
	reverse(s.begin(),s.end());
	cout << s;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= 2*n; i++) cin >> a[i];
	for(int i = 1; i <= 2*n; i++) cin >> b[i];
	memset(dp1,-1,sizeof(dp1));
	for(int i = 1; i <= 2*n; i++){
		for(int j = 0; j <= 1; j++) dp2[i][j] = 1e9;
	}
	dp1[0][0] = 0;
	dp1[0][1] = 0;
	for(int i = 1; i <= 2*n; i++){
		if(a[i] >= a[i-1]){
			dp1[i][0] = max(dp1[i][0],dp1[i-1][0]+1);
			dp2[i][0] = min(dp2[i][0],dp2[i-1][0]+1);
		}
		if(a[i] >= b[i-1]){
			dp1[i][0] = max(dp1[i][0],dp1[i-1][1]+1);
			dp2[i][0] = min(dp2[i][0],dp2[i-1][1]+1);
		}
		if(b[i] >= a[i-1]){
			dp1[i][1] = max(dp1[i][1],dp1[i-1][0]);
			dp2[i][1] = min(dp2[i][1],dp2[i-1][0]);
		}
		if(b[i] >= b[i-1]){
			dp1[i][1] = max(dp1[i][1],dp1[i-1][1]);
			dp2[i][1] = min(dp2[i][1],dp2[i-1][1]);
		}
	}
	if(dp1[2*n][0] >= n && dp2[2*n][0] <= n) trace(2*n,0,n-1);
	else if(dp1[2*n][1] >= n && dp2[2*n][1] <= n) trace(2*n,1,n);
	else cout << -1;
}

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