#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 1e6 + 5;
const int INF = 1e9;
int n, Q;
int dpl[maxn][2], dpr[maxn][2]; // # of A used
int main(void){
fastio;
int n;
cin>>n;
n *= 2;
vector<int> a(n), b(n), no(n), no2(n), ou(n);
for(int i = 0; i < n; i++) cin>>a[i];
for(int i = 0; i < n; i++) cin>>b[i];
// type 0 : 2, 2 / type 1 : 2, 1 / type 2 : 1, 1 / type 3 : 1, 0
dpl[0][0] = dpr[0][0] = 1;
dpl[0][1] = dpr[0][1] = 0;
for(int i = 1; i < n; i++){
dpl[i][0] = dpl[i][1] = INF;
dpr[i][0] = dpr[i][1] = -1;
if(a[i - 1] <= a[i]) dpl[i][0] = dpl[i - 1][0] + 1, dpr[i][0] = dpr[i - 1][0] + 1;
if(b[i - 1] <= a[i]) ckmin(dpl[i][0], dpl[i - 1][1] + 1), ckmax(dpr[i][0], dpr[i - 1][1] + 1);
if(b[i - 1] <= b[i]) dpl[i][1] = dpl[i - 1][1], dpr[i][1] = dpr[i - 1][1];
if(a[i - 1] <= b[i]) ckmin(dpl[i][1], dpl[i - 1][0]), ckmax(dpr[i][1], dpr[i - 1][0]);
}
int bad = 0;
if(dpl[n - 1][0] > n / 2 && dpl[n - 1][1] > n / 2) bad = 1;
if(dpr[n - 1][0] < n / 2 && dpr[n - 1][1] < n / 2) bad = 1;
if(bad){
cout<<-1<<"\n";
return 0;
}
int pos = 0;
if(dpl[n - 1][1] <= n / 2 && dpr[n - 1][1] >= n / 2) pos = 1;
string ans = "";
ans += char('A' + pos);
int need = n / 2 - 1 + pos;
for(int i = n - 2; i >= 0; i--){
if(dpl[i][0] <= need && dpr[i][0] >= need && a[i] <= (pos ? b[i + 1] : a[i + 1])) pos = 0;
else pos = 1;
ans += char('A' + pos);
need = need - 1 + pos;
}
reverse(ans.begin(), ans.end());
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
187 ms |
35408 KB |
Output is correct |
| 35 |
Correct |
159 ms |
53520 KB |
Output is correct |
| 36 |
Correct |
171 ms |
52748 KB |
Output is correct |
| 37 |
Correct |
160 ms |
53576 KB |
Output is correct |
| 38 |
Correct |
150 ms |
53772 KB |
Output is correct |
| 39 |
Correct |
148 ms |
52860 KB |
Output is correct |
| 40 |
Correct |
159 ms |
56544 KB |
Output is correct |
| 41 |
Correct |
157 ms |
53820 KB |
Output is correct |
| 42 |
Correct |
173 ms |
55448 KB |
Output is correct |
| 43 |
Correct |
173 ms |
57036 KB |
Output is correct |
| 44 |
Correct |
185 ms |
56912 KB |
Output is correct |
| 45 |
Correct |
183 ms |
57140 KB |
Output is correct |
| 46 |
Correct |
160 ms |
57416 KB |
Output is correct |
| 47 |
Correct |
160 ms |
56136 KB |
Output is correct |
| 48 |
Correct |
182 ms |
56000 KB |
Output is correct |
| 49 |
Correct |
167 ms |
56904 KB |
Output is correct |
| 50 |
Correct |
175 ms |
56092 KB |
Output is correct |
| 51 |
Correct |
169 ms |
56188 KB |
Output is correct |
| 52 |
Correct |
118 ms |
45252 KB |
Output is correct |
| 53 |
Correct |
118 ms |
45364 KB |
Output is correct |
| 54 |
Correct |
110 ms |
45384 KB |
Output is correct |
| 55 |
Correct |
111 ms |
45352 KB |
Output is correct |
| 56 |
Correct |
171 ms |
57180 KB |
Output is correct |
| 57 |
Correct |
159 ms |
52024 KB |
Output is correct |
| 58 |
Correct |
139 ms |
52140 KB |
Output is correct |
| 59 |
Correct |
137 ms |
52268 KB |
Output is correct |
| 60 |
Correct |
132 ms |
49996 KB |
Output is correct |
| 61 |
Correct |
160 ms |
52700 KB |
Output is correct |
| 62 |
Correct |
147 ms |
52020 KB |
Output is correct |
| 63 |
Correct |
161 ms |
52812 KB |
Output is correct |
| 64 |
Correct |
170 ms |
51216 KB |
Output is correct |
| 65 |
Correct |
158 ms |
52784 KB |
Output is correct |
