| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 337101 | rocks03 | Building 4 (JOI20_building4) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e6+100;
int N, a[MAXN], b[MAXN];
struct state{
bool good = false;
int l[2] = {MAXN, MAXN}, r[2] = {-1, -1};
} dp[2][MAXN];
void solve(){
cin >> N;
N = 2 * N;
for(int i = 0; i < N; i++){
cin >> a[i];
}
for(int i = 0; i < N; i++){
cin >> b[i];
}
dp[0][0].good = dp[1][0].good = true;
dp[0][0].l[0] = dp[0][0].r[0] = 1;
dp[0][0].l[1] = dp[0][0].r[1] = 0;
dp[1][0].l[0] = dp[1][0].r[0] = 0;
dp[1][0].l[1] = dp[1][0].r[1] = 1;
for(int i = 1; i < N; i++){
if(max(a[i], b[i]) < min(a[i-1], b[i-1])){
cout << "-1";
return;
}
if(a[i] >= a[i-1] && dp[0][i-1].good){
dp[0][i].good = true;
dp[0][i].l[0] = min(dp[0][i].l[0], dp[0][i-1].l[0] + 1);
dp[0][i].r[0] = max(dp[0][i].r[0], dp[0][i-1].r[0] + 1);
dp[0][i].l[1] = min(dp[0][i].l[1], dp[0][i-1].l[1]);
dp[0][i].r[1] = max(dp[0][i].r[1], dp[0][i-1].r[1]);
}
if(a[i] >= b[i-1] && dp[1][i-1].good){
dp[0][i].good = true;
dp[0][i].l[0] = min(dp[0][i].l[0], dp[1][i-1].l[0] + 1);
dp[0][i].r[0] = max(dp[0][i].r[0], dp[1][i-1].r[0] + 1);
dp[0][i].l[1] = min(dp[0][i].l[1], dp[1][i-1].l[1]);
dp[0][i].r[1] = max(dp[0][i].r[1], dp[1][i-1].r[1]);
}
if(b[i] >= a[i-1] && dp[0][i-1].good){
dp[1][i].good = true;
dp[1][i].l[0] = min(dp[1][i].l[0], dp[0][i-1].l[0]);
dp[1][i].r[0] = max(dp[1][i].r[0], dp[0][i-1].r[0]);
dp[1][i].l[1] = min(dp[1][i].l[1], dp[0][i-1].l[1] + 1);
dp[1][i].r[1] = max(dp[1][i].r[1], dp[0][i-1].r[1] + 1);
}
if(b[i] >= b[i-1] && dp[1][i-1].good){
dp[1][i].good = true;
dp[1][i].l[0] = min(dp[1][i].l[0], dp[1][i-1].l[0]);
dp[1][i].r[0] = max(dp[1][i].r[0], dp[1][i-1].r[0]);
dp[1][i].l[1] = min(dp[1][i].l[1], dp[1][i-1].l[1] + 1);
dp[1][i].r[1] = max(dp[1][i].r[1], dp[1][i-1].r[1] + 1);
}
if(!dp[0][i].good && !dp[1][i].good){
cout << "-1";
return;
}
}
string ans = "";
int A = N / 2, B = N / 2, mx = INT_MAX;
for(int i = N - 1; i >= 0; i--){
if(a[i] > mx && b[i] > mx){
cout << "-1";
return;
}
if(A == 0){
if(b[i] <= mx){
B--;
ans += 'B';
mx = b[i];
continue;
}
cout << "-1";
return;
}
if(B == 0){
if(a[i] <= mx){
A--;
ans += 'A';
mx = a[i];
continue;
}
cout << "-1";
return;
}
if(a[i] <= mx){
if(dp[0][i].l[0] <= A && A <= dp[0][i].r[0] && dp[0][i].l[1] <= B && B <= dp[0][i].r[1]){
A--;
ans += 'A';
mx = a[i];
continue;
}
}
if(b[i] <= mx){
if(dp[1][i].l[0] <= A && A <= dp[1][i].r[0] && dp[1][i].l[1] <= B && B <= dp[1][i].r[1]){
B--;
ans += 'B';
mx = b[i];
continue;
}
}
cout << "-1";
return;
}
reverse(all(ans));
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}