Submission #1019202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019202		Nurislam	Building 4 (JOI20_building4)	C++17	100 / 100	226 ms	76872 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>  
#define int long long

const int N = 1e6+5, inf = 1e16, mod = 1e9+7;
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
void solve(){
	int n;
	cin >> n;
	vector<int> a(n*2+2, 0), b(n*2+2, 0);
	for(int i = 1; i <= n*2; i++)cin >>  a[i];
	for(int i = 1; i <= n*2; i++)cin >>  b[i];
	pair<int,int> dp[n*2+1][2];
	for(int i = 1; i <= n*2; i++){
		dp[i][0] = dp[i][1] = {-1,-1};
	}
	dp[1][0] = {1, 1};
	dp[1][1] = {0, 0};
	for(int i = 2; i <= n*2; i++){
		if(a[i] >= a[i-1] && dp[i-1][0].ff != -1){
			if(dp[i][0].ff == -1){
				dp[i][0].ff = dp[i-1][0].ff+1;
				dp[i][0].ss = dp[i-1][0].ss+1;
			}else{
				chmin(dp[i][0].ff,dp[i-1][0].ff+1);
				chmax(dp[i][0].ss,dp[i-1][0].ss+1);
			}
		}
		if(a[i] >= b[i-1] && dp[i-1][1].ff != -1){
			if(dp[i][0].ff == -1){
				dp[i][0].ff = dp[i-1][1].ff+1;
				dp[i][0].ss = dp[i-1][1].ss+1;
			}else{
				chmin(dp[i][0].ff,dp[i-1][1].ff+1);
				chmax(dp[i][0].ss,dp[i-1][1].ss+1);
			}
		}
		// 
		
		 if(b[i] >= a[i-1] && dp[i-1][0].ff != -1){
			if(dp[i][1].ff == -1){
				dp[i][1].ff = dp[i-1][0].ff;
				dp[i][1].ss = dp[i-1][0].ss;
			}else{
				chmin(dp[i][1].ff,dp[i-1][0].ff);
				chmax(dp[i][1].ss,dp[i-1][0].ss);
			}
		}
		if(b[i] >= b[i-1] && dp[i-1][1].ff != -1){
			if(dp[i][1].ff == -1){
				dp[i][1].ff = dp[i-1][1].ff;
				dp[i][1].ss = dp[i-1][1].ss;
			}else{
				chmin(dp[i][1].ff,dp[i-1][1].ff);
				chmax(dp[i][1].ss,dp[i-1][1].ss);
			}	
		}
	}
	
	//for(int i=1;i<=2*n;i++) {
        //cout<<dp[i][0].ff<<' '<<dp[i][0].ss<<"    "<<dp[i][1].ff<<' '<<dp[i][1].ss<<endl;
    //}
	if(dp[n*2][0].ff <= n && dp[n*2][0].ss >= n){
		vector<int> ans;
		int cur = n, t = 0;
		for(int i = n*2; i >= 0; i--){
			if(t == 0){cur--;ans.pb(1);}
			else ans.pb(0);
			if(i == 1)break;
			if(t == 0){
				if(dp[i-1][0].ff <= cur && dp[i-1][0].ss >= cur && a[i-1] <= a[i]){
					t = 0;
				}else if(dp[i-1][1].ff <= cur && dp[i-1][1].ss >= cur && b[i-1] <= a[i]){
					t = 1;
				}
			}
			else{
				if(dp[i-1][0].ff <= cur && dp[i-1][0].ss >= cur && a[i-1] <= b[i]){
					t = 0;
				}else if(dp[i-1][1].ff <= cur && dp[i-1][1].ss >= cur && b[i-1] <= b[i]){
					t = 1;
				}
			}
		}
		reverse(all(ans));
		for(auto i:ans){
			cout << (i==1?"A":"B");
		}
	}else if(dp[n*2][1].ff <= n && dp[n*2][1].ss >= n){
		vector<int> ans;
		int cur = n, t = 1;
		for(int i = n*2; i >= 0; i--){
			if(t == 0){cur--;ans.pb(1);}
			else ans.pb(0);
			if(i == 1)break;
			if(t == 0){
				if(dp[i-1][0].ff <= cur && dp[i-1][0].ss >= cur && a[i-1] <= a[i]){
					t = 0;
				}else if(dp[i-1][1].ff <= cur && dp[i-1][1].ss >= cur && b[i-1] <= a[i]){
					t = 1;
				}
			}
			else{
				if(dp[i-1][0].ff <= cur && dp[i-1][0].ss >= cur && a[i-1] <= b[i]){
					t = 0;
				}else if(dp[i-1][1].ff <= cur && dp[i-1][1].ss >= cur && b[i-1] <= b[i]){
					t = 1;
				}
			}
		}
		reverse(all(ans));
		for(auto i:ans){
			cout << (i==1?"A":"B");
		}
	}else{
		cout << -1;
	}cout << '\n';
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

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