Submission #979457

#	Time	Username	Problem	Language	Result	Execution time	Memory
979457		happy_node	Building 4 (JOI20_building4)	C++17	100 / 100	209 ms	45388 KiB

building4

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

const int MX=1e6+5;

int N;
int A[MX][2], L[MX][2], R[MX][2];

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

	int N;
	cin>>N;
	for(int i=0;i<2*N;i++) cin>>A[i][0];
	for(int i=0;i<2*N;i++) cin>>A[i][1];

	L[0][0]=0;
	R[0][0]=0;
	L[0][1]=1;
	R[0][1]=1;

	for(int i=1;i<2*N;i++) {
		for(int j=0;j<2;j++) {
			L[i][j]=1e9;
			R[i][j]=0;
		}
	}

	for(int i=1;i<2*N;i++) {
		for(int j=0;j<2;j++) {
			for(int k=0;k<2;k++) {
				if(A[i-1][k]<=A[i][j]) {
					L[i][j]=min(L[i][j],L[i-1][k]+j);
					R[i][j]=max(R[i][j],R[i-1][k]+j);
				}
			}
		}
	}

	if(L[2*N-1][0]<=N && N<=R[2*N-1][0]) {
		string ans="";
		ans+='A';
		int cur=N, prv=A[2*N-1][0];
		for(int i=2*N-2;i>=0;i--) {
			if(L[i][0]<=cur && cur<=R[i][0] && A[i][0]<=prv) {
				ans+='A';
				prv=A[i][0];
			} else {
				cur-=1;
				ans+='B';
				prv=A[i][1];
			}
		}
		reverse(ans.begin(),ans.end());
		cout<<ans<<'\n';
	} else if(L[2*N-1][1]<=N && N<=R[2*N-1][1]) {
		string ans="";
		ans+='B';
		int cur=N-1, prv=A[2*N-1][1];
		for(int i=2*N-2;i>=0;i--) {
			if(L[i][0]<=cur && cur<=R[i][0] && A[i][0]<=prv) {
				ans+='A';
				prv=A[i][0];
			} else {
				cur-=1;
				ans+='B';
				prv=A[i][1];
			}
		}
		reverse(ans.begin(),ans.end());
		cout<<ans<<'\n';
	} else {
		cout<<-1<<'\n';
	}

}

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