#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
#define ld long double
using namespace std;
bool visited[1000000][2], X[1000000][2], B[1000000];
string S;
vector <array<ll, 2>> V, R;
ll n, s, k, p, x, mn, mx, A[1000000][2], cnt[1000000];
void dfs(ll u, ll x) {
visited[u][x] = 1;
if (u == n-1) {
X[u][x] = 1;
return;
}
if (A[u][x] <= A[u+1][0]) {
if (!visited[u+1][0]) dfs(u+1, 0);
X[u][x] |= X[u+1][0];
}
if (A[u][x] <= A[u+1][1]) {
if (!visited[u+1][1]) dfs(u+1, 1);
X[u][x] |= X[u+1][1];
}
}
int main() {
cin >> n;
n *= 2;
for (int j=0; j<2; ++j) {
for (int i=0; i<n; ++i) cin >> A[i][j];
}
dfs(0, 0);
dfs(0, 1);
if (!X[0][0] && !X[0][1]) {
cout << "-1\n";
return 0;
}
for (int i=0; i<n; ++i) {
S += '.';
cnt[i] = X[i][0] + X[i][1];
if (cnt[i] == 1) {
if (X[i][0]) {
S.back() = 'A';
++s;
}
else {
S.back() = 'B';
--s;
}
}
}
k = 0, p = 1e18;
for (ll i=0; i+1<n; ++i) {
if (cnt[i] == 1 || cnt[i+1] == 1 || max(A[i][0], A[i][1]) <= min(A[i+1][0], A[i+1][1])) {
if (p != 1e18) {
if (A[i][0] > A[i][1]) ++k;
else --k;
mn = mx = k;
for (int j=p; j<=i; ++j) {
B[j] = 1;
if (A[j][0] > A[j][1]) k -= 2;
else k += 2;
mn = min(mn, k);
mx = max(mx, k);
}
R.push_back({p, i});
V.push_back({mn, mx});
k = 0, p = 1e18;
}
continue;
}
p = min(p, i);
if (A[i][0] > A[i][1]) ++k;
else --k;
}
if (p != 1e18) {
mn = mx = k;
for (int j=p; j<n; ++j) {
if (A[j][0] > A[j][1]) k -= 2;
else k += 2;
mn = min(mn, k);
mx = max(mx, k);
}
V.push_back({mn, mx});
k = 0, p = 1e18;
}
k = 0;
for (int i=0; i<n; ++i) {
if (cnt[i] == 2 && !B[i]) ++k;
}
for (auto [l, r] : V) {
s += l;
}
for (auto &[l, r] : V) {
while (s < 0 && l < r) {
s += 2;
l += 2;
}
}
if (s + k < 0 || s - k > 0) {
cout << "-1\n";
return 0;
}
int i = 0;
for (auto [l, r] : R) {
x = 0;
for (int i=l; i<=r; ++i) {
if (A[i][0] > A[i][1]) {
S[i] = 'A';
++x;
}
else {
S[i] = 'B';
--x;
}
}
if (x == V[i][0]) continue;
for (int i=l; i<=r; ++i) {
if (A[i][0] > A[i][1]) {
S[i] = 'B';
x -= 2;
}
else {
S[i] = 'A';
x += 2;
}
if (x == V[i][0]) break;
}
++i;
}
for (int i=0; i<n; ++i) {
if (cnt[i] == 2 && !B[i]) {
if (s <= 0) {
++s;
S[i] = 'A';
}
else {
--s;
S[i] = 'B';
}
}
}
cout << S << '\n';
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:95:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
95 | for (auto [l, r] : V) {
| ^
building4.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | for (auto &[l, r] : V) {
| ^
building4.cpp:109:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for (auto [l, r] : R) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6488 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6744 KB |
Output is correct |
5 |
Correct |
5 ms |
6636 KB |
Output is correct |
6 |
Correct |
5 ms |
6892 KB |
Output is correct |
7 |
Correct |
3 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
6748 KB |
Output is correct |
9 |
Correct |
4 ms |
6748 KB |
Output is correct |
10 |
Incorrect |
3 ms |
6744 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6488 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
6744 KB |
Output is correct |
5 |
Correct |
5 ms |
6636 KB |
Output is correct |
6 |
Correct |
5 ms |
6892 KB |
Output is correct |
7 |
Correct |
3 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
6748 KB |
Output is correct |
9 |
Correct |
4 ms |
6748 KB |
Output is correct |
10 |
Incorrect |
3 ms |
6744 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |