Submission #1008822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008822		goduadzesaba	Building 4 (JOI20_building4)	C++17	100 / 100	184 ms	68912 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,a[N],b[N],dl[N][2],dr[N][2],cnt;
string s;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n; a[2*n+1]=b[2*n+1]=1e9+1;
	for (int i=1; i<=2*n; i++) cin>>a[i];
	for (int i=1; i<=2*n; i++) cin>>b[i];
	dl[0][0]=dl[0][1]=dr[0][0]=dr[0][1]=0;
	for (int i=1; i<=2*n; i++){
		dl[i][0]=dl[i][1]=2*n;
		dr[i][0]=dr[i][1]=-1;
		if (a[i]>=a[i-1]){
			dl[i][0]=min(dl[i][0],dl[i-1][0]+1);
			dr[i][0]=max(dr[i][0],dr[i-1][0]+1);
		}
		if (a[i]>=b[i-1]){
			dl[i][0]=min(dl[i][0],dl[i-1][1]+1);
			dr[i][0]=max(dr[i][0],dr[i-1][1]+1);
		}
		if (b[i]>=a[i-1]){
			dl[i][1]=min(dl[i][1],dl[i-1][0]);
			dr[i][1]=max(dr[i][1],dr[i-1][0]);
		}
		if (b[i]>=b[i-1]){
			dl[i][1]=min(dl[i][1],dl[i-1][1]);
			dr[i][1]=max(dr[i][1],dr[i-1][1]);
		}
	}
	if (!(dl[2*n][0]<=n && n<=dr[2*n][0]) && !(dl[2*n][1]<=n && n<=dr[2*n][1])){
		cout<<-1; return 0;
	}
	cnt=n;
	for (int i=2*n; i>0; i--){
		if (dl[i][0]<=cnt && cnt<=dr[i][0] && (s.empty() || (s[(int)s.size()-1]=='A' && a[i]<=a[i+1]) || (s[(int)s.size()-1]=='B' && a[i]<=b[i+1]))){
			cnt--; s+="A";
		}
		else{
			s+="B";
		}
	}
	reverse(s.begin(),s.end()); cout<<s;
}

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