Submission #231625

#	Time	Username	Problem	Language	Result	Execution time	Memory
231625		jiahng	Building 4 (JOI20_building4)	C++14	100 / 100	346 ms	83692 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 1000001
#define INF 1e9
#define int ll

int N,M;
int dp[maxn][2],val[maxn][2],A[maxn],B[maxn];
int mx[maxn][2],mn[maxn][2];
static int _max(int i,int j){
	if (i == INF) return j;
	if (j == INF) return i;
	return max(i,j);
}
static int _min(int i,int j){
	if (i == INF) return j;
	if (j == INF) return i;
	return min(i,j);
}
 
int32_t main(){
	fast;
	
	cin>>N;
	M = 2 * N;
	
	FOR(i,1,M){
		cin>>A[i];
		val[i][0] = A[i];
		mx[i][0] = mx[i][1] = mn[i][0] = mn[i][1] = INF;
	}
	FOR(i,1,M){
		cin>>B[i];
		val[i][1]= B[i];
	}
	
	mx[1][0] = mn[1][0] = 1;
	mx[1][1] = mn[1][1] = -1;
	
	FOR(i,2,M){
		FOR(j,0,1){
			if (val[i - 1][0] <= val[i][j]){
				mx[i][j] = _max(mx[i][j],mx[i-1][0]);
				mn[i][j] = _min(mn[i][j],mn[i-1][0]);
			}
			if (val[i - 1][1] <= val[i][j]){
				mx[i][j] = _max(mx[i][j],mx[i-1][1]);
				mn[i][j] = _min(mn[i][j],mn[i-1][1]);
			}
			
			if (mx[i][j] != INF && mn[i][j] != INF){
				if (j == 0){
					mx[i][j]++;
					mn[i][j]++;
				}else{
					mx[i][j]--;
					mn[i][j]--;
				}
			}
		}
	}
	
	//~ FOR(i,1,M){
		//~ FOR(j,0,1) cout<<mx[i][j]<<' '<<mn[i][j]<<' ';
		//~ cout<<'\n';
	//~ }
	
	FOR(k,0,1){
		if (!(mn[M][k] <= 0 && 0 <= mx[M][k])) continue;
		
		string ans = "";
		int cur=0,curguy = k;
		
		
		
		DEC(i,M,1){
			int desired = cur;
			if (curguy == 0){
				ans += 'A';
				desired--;
			}else{
				ans += 'B';
				desired++;
			}
			
			if (i == 1) break;
			FOR(j,0,1){
				
				if (mn[i-1][j] <= desired && desired <= mx[i-1][j] && val[i-1][j] <= val[i][curguy]){
					cur = desired;
					curguy = j;
					break;
				}
			}
		}
		
		reverse(all(ans));
		cout<<ans;
		return 0;
	}
	cout<<-1;
}

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