Submission #1015569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015569		ByeWorld	Building 4 (JOI20_building4)	C++14	100 / 100	213 ms	101452 KiB

building4

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 2e6+20;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmx(int &a, int b){
	a = max(a, b);
}
int n;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int x[MAXN], y[MAXN];

int idx = -1;
void cek(int xx){
	if((a[xx]<=0 && 0<=b[xx]) || (c[xx]<=0 && 0<=d[xx])) idx = xx;
}
void solve(int i, int la, int ty){
	if(x[la] <= x[i]){
		if(a[la]!=-INF && c[la]!=INF){
			a[i] = a[la]+ty; b[i] = d[la]+ty;
		} else if(a[la]!=-INF){
			a[i] = a[la]+ty; b[i] = b[la]+ty;
		} else if(c[la]!=INF){
			a[i] = c[la]+ty; b[i] = d[la]+ty;
		}
	}
}
void solve2(int i, int lb, int ty){
	if(x[lb] <= x[i]){
		// cout << i << " ikena\n";
		if(a[lb]!=-INF && c[lb]!=INF){
			c[i] = a[lb]+ty; d[i] = d[lb]+ty;
		} else if(a[lb]!=-INF){
			c[i] = a[lb]+ty; d[i] = b[lb]+ty;
		} else if(c[lb]!=INF){
			c[i] = c[lb]+ty; d[i] = d[lb]+ty;
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n; n *= 2;
	for(int i=1; i<=2*n; i+=2) cin >> x[i];
	for(int i=2; i<=2*n; i+=2) cin >> x[i];
	for(int i=1; i<=2*n; i++){
		a[i] = -INF; b[i] = -INF; c[i] = INF; d[i] = INF;
	}
	{
		a[1] = b[1] = -1;
		c[2] = d[2] = 1;
	}
	for(int i=3; i<=2*n; i++){
		int la = i-2, lb=i-1, ty = -1;
		if(i%2==0){
			// bawah +1
			la--; lb--;
			ty = 1;
		}
		// la
		solve(i, la, ty);
		// lb
		solve2(i, lb, ty);
		if(a[i]<=c[i]&&d[i]<=b[i]){
			c[i] = d[i] = INF;
		}
		if(c[i]<=a[i]&&b[i]<=d[i]){
			a[i] = b[i] = -INF;
		}
		// cout << i << "i\n";
		// cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << " xx\n";
		
		if(b[i]!=-INF && c[i]!=INF) c[i] = b[i]+2;
		
		// cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << " xx\n";
	} 
	cek(2*n-1); cek(2*n);
	if(idx==-1){ cout << "-1\n"; exit(0); }

	string ans = "";
	int nw = idx, val = 0;
	// cout << idx << " idx\n";
	while(1<=nw){
		ans += (nw%2 ? 'A' : 'B');
		int te = (nw%2 ? 1 : -1);

		if(a[nw]<=val && val<=b[nw]){
			if(nw%2==0) nw--;
			nw -= 2;
			val += te;
		} else {
			if(nw%2==0) nw--;
			nw--;
			val += te;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans << '\n';
}
/*
2
3 4 5 6
10 9 8 7
3
2 5 4 9 15 11
6 7 6 8 12 14

6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78
BABBABAABABA
// 19 aneh
*/

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