Submission #892776

#	Time	Username	Problem	Language	Result	Execution time	Memory
892776		amirhoseinfar1385	Building 4 (JOI20_building4)	C++17	100 / 100	161 ms	26008 KiB

building4

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int n;
int dpl[maxn][2],dpr[maxn][2],all[maxn][2];
string res;

void cal(int ind,int vas,int ted=n){
	while(true){
	if(vas==1){
		res.push_back('B');
		ted--;
	}
	else{
		res.push_back('A');
	}
	if(ind==0){
		return ;
	}
	if(all[ind-1][vas]<=all[ind][vas]&&dpl[ind-1][vas]<=ted&&dpr[ind-1][vas]>=ted){
		ind--;
	}
	else{
		vas^=1;
		ind--;
	}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	n*=2;
	for(int i=0;i<n;i++){
		cin>>all[i][0];
	}
	for(int i=0;i<n;i++){
		cin>>all[i][1];
	}
	dpl[0][0]=dpr[0][0]=0;
	dpl[0][1]=dpr[0][1]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<2;j++){
			dpl[i][j]=maxn+10;
			dpr[i][j]=-1;
			if(dpr[i-1][j]!=-1&&all[i-1][j]<=all[i][j]){
				dpl[i][j]=dpl[i-1][j];
				dpr[i][j]=dpr[i-1][j];
			}
			if(dpr[i-1][j^1]!=-1&&all[i-1][j^1]<=all[i][j]){
				dpl[i][j]=min(dpl[i][j],dpl[i-1][j^1]);
				dpr[i][j]=max(dpr[i][j],dpr[i-1][j^1]);
			}
			if(dpr[i][j]!=-1&&j==1){
				dpr[i][j]++;
				dpl[i][j]++;
			}
		//	cout<<i<<" "<<j<<" "<<dpl[i][j]<<" "<<dpr[i][j]<<"\n";
		}
	}
	n/=2;
	if(n>=dpl[2*n-1][0]&&n<=dpr[2*n-1][0]){
		cal(2*n-1,0);
		reverse(res.begin(),res.end());
		cout<<res<<"\n";
		return 0;
	}
	if(n>=dpl[2*n-1][1]&&n<=dpr[2*n-1][1]){
		cal(2*n-1,1);
		reverse(res.begin(),res.end());
		cout<<res<<"\n";
		return 0;
	}
	cout<<-1<<"\n";
	return 0;
}

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