# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1228223 | RakhimovAmir | Building 4 (JOI20_building4) | C++20 | 1 ms | 320 KiB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void debugMode() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
void solve() {
int n, inf = 1e9;
cin >> n;
int a[2 * n][2];
int mn[2 * n][2], mx[2 * n][2];
for (int i = 0; i < 2 * n; i++) {
cin >> a[i][0];
mn[i][0] = mn[i][1] = inf;
mx[i][0] = mx[i][1] = -inf;
}
for (int i = 0; i < 2 * n; i++) {
cin >> a[i][1];
}
mn[0][0] = 0;
mn[0][1] = 1;
mx[0][0] = 0;
mx[0][1] = 1;
for (int i = 1; i < 2 * n; i++) {
for (int j = 0; j < 2; j++) {
for (int g = 0; g < 2; g++) {
if (a[i][j] < a[i - 1][g])
continue;
mn[i][j] = min(mn[i][j], mn[i - 1][g] + j);
mx[i][j] = max(mx[i][j], mx[i - 1][g] + j);
}
// cout << mn[i][j] << " " << mx[i][j] << " ";
}
// cout << "\n";
}
for (int z = 0; z < 2; z++) {
if (mn[2 * n - 1][z] > n || mx[2 * n - 1][z] < n)
continue;
int now = z, need = n;
vector<char> v;
for (int i = 2 * n - 1; i >= 0; i--) {
// cout << now << " " << need << " " << mn[i][now] << " " << mx[i][now] << "\n";
if (mn[i][now] > need || mx[i][now] < need)
now ^= 1;
need -= now;
v.push_back((now ? 'B' : 'A'));
}
reverse(v.begin(), v.end());
for (auto i : v)
cout << i;
return;
}
cout << -1;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
debugMode();
int $ = 1;
// cin >> $;
while ($--) {
solve();
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |