Submission #211502

#	Time	Username	Problem	Language	Result	Execution time	Memory
211502		kostia244	Building 4 (JOI20_building4)	C++17	100 / 100	368 ms	88816 KiB

building4

#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
const int maxn = 1005000 + 22, mod = 998244353;
int n, a[maxn], b[maxn], mn[maxn][2], mx[maxn][2];
string ans;

bool bt(int v, int l, int bl = n/2, int lst = 2e9) {
	if(bl<0||v<bl||(v && (l?b:a)[v-1]>lst)) return false;
	if(bl>mx[v][l]||bl<mn[v][l]) return false;
	if(!v) return true;
	if(!bt(v-1, 0, bl - (l==1), (l?b:a)[v-1])&&!bt(v-1, 1, bl - (l==1), (l?b:a)[v-1])) return 0;
	//cout << v << " " << l << " " << bl << '\n';
	ans += "AB"[l];
	return true;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	n *= 2;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> b[i];
	memset(mn, 0x3f, sizeof mn);
	memset(mx, -0x3f, sizeof mx);
	mn[0][0] = mx[0][0] = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 2; j++) {
			int lst = (i?(j?b:a)[i-1]:0);
			if(a[i]>=lst) {
				mn[i+1][0] = min(mn[i+1][0], mn[i][j]);
				mx[i+1][0] = max(mx[i+1][0], mx[i][j]);
			}
			if(b[i]>=lst) {
				mn[i+1][1] = min(mn[i+1][1], mn[i][j]+1);
				mx[i+1][1] = max(mx[i+1][1], mx[i][j]+1);
			}
		}
	}
	if(!bt(n, 0)&&!bt(n, 1)) cout << -1;
	cout << ans << '\n';
}

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