// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e6 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
int n, A[2][N];
int O[2][N];
int mk[N];
int main(){
scanf("%d", &n);
n += n;
for(int it = 0; it < 2; it ++){
for(int i = 0; i < n; i++){
scanf("%d", A[it] + i);
O[it][i] = true;
}
}
for(int i = 1; i < n; i++){
for(int lv = 0; lv < 2; lv ++){
O[lv][i] &= (A[0][i - 1] <= A[lv][i] && O[0][i - 1]) || (A[1][i - 1] <= A[lv][i] && O[1][i - 1]);
}
}
for(int i = n - 2; i >= 0; i--){
for(int lv = 0; lv < 2; lv ++){
O[lv][i] &= (A[0][i + 1] >= A[lv][i] && O[0][i + 1]) || (A[1][i + 1] >= A[lv][i] && O[1][i + 1]);
}
}
for(int i = 0; i < n; i++)
if(!O[0][i] && !O[1][i]) return !printf("-1\n");
int sm = 0;
for(int i = 0; i < n; i++){
if(O[0][i] && !O[1][i]) sm ++;
else if(!O[0][i] && O[1][i]) sm --;
else {
if(A[0][i] <= A[1][i]) sm ++;
else sm --;
}
}
bool flg = false;
if(sm < 0){
sm = -sm;
swap(A[0], A[1]);
swap(O[0], O[1]);
flg = true;
}
int po = 0;
int Sm = 0;
vector<pll> V;
//cerr << "# " << sm << '\n';
for(int i = 0; i < n; ){
if(O[0][i] && !O[1][i]){
po ++; i = po; continue;
}
if(!O[0][i] && O[1][i]){
po ++; i = po; continue;
}
while((po + 1 < n) && (O[0][po + 1] && O[1][po + 1]) && (max(A[0][po], A[1][po]) > min(A[0][po + 1], A[1][po + 1])) ) po ++;
//cerr << "! " << i << ' ' << po << '\n';
int nw = 0, mn = 0, v, idx = po + 1;
for(int j = po; j >= i; j--){
v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) );
nw -= 2 * v;
if(nw < mn){
idx = j;
mn = nw;
}
}
if(mn < 0){
Sm += mn;
V.pb({po, idx});
}
po ++;
i = po;
}
//cerr << Sm << '\n';
if(Sm + sm > 0) return !printf("-1\n");
//debug(V.size());
for(auto [P, i] : V){
int v;
for(int j = P; j >= i; j--){
if(sm == 0) break;
v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) );
sm -= 2 * v;
mk[j] = 1;
}
}
if(flg){
swap(A[0], A[1]);
swap(O[0], O[1]);
}
int out = 0;
vector<int> I;
for(int i = 0; i < n; i++){
//if(mk[i]) debug(i);
int mn;
if(!O[0][i]) mn = 1;
else if(!O[1][i]) mn = 0;
else mn = (A[0][i] <= A[1][i] ? 0 : 1);
if(mk[i]) mn = 1 - mn;
if(mn == 0) out ++, printf("A");
if(mn == 1) out --, printf("B");
I.pb(A[mn][i]);
}
for(int i = 0; i + 1 < n; i++) assert(I[i] <= I[i + 1]);
assert(out == 0);
printf("\n");
return 0;
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
building4.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", A[it] + i);
~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
15 ms |
16000 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
16 ms |
16128 KB |
Output is correct |
9 |
Correct |
21 ms |
16128 KB |
Output is correct |
10 |
Correct |
21 ms |
16128 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
560 KB |
Output is correct |
13 |
Correct |
3 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
18 ms |
16128 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
21 ms |
16128 KB |
Output is correct |
19 |
Correct |
3 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
16 ms |
16128 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
512 KB |
Output is correct |
27 |
Correct |
2 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
512 KB |
Output is correct |
29 |
Correct |
2 ms |
512 KB |
Output is correct |
30 |
Correct |
2 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
512 KB |
Output is correct |
32 |
Correct |
2 ms |
512 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
15 ms |
16000 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
16 ms |
16128 KB |
Output is correct |
9 |
Correct |
21 ms |
16128 KB |
Output is correct |
10 |
Correct |
21 ms |
16128 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
560 KB |
Output is correct |
13 |
Correct |
3 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
18 ms |
16128 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
21 ms |
16128 KB |
Output is correct |
19 |
Correct |
3 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
16 ms |
16128 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
512 KB |
Output is correct |
27 |
Correct |
2 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
512 KB |
Output is correct |
29 |
Correct |
2 ms |
512 KB |
Output is correct |
30 |
Correct |
2 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
512 KB |
Output is correct |
32 |
Correct |
2 ms |
512 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
34 |
Correct |
409 ms |
16120 KB |
Output is correct |
35 |
Correct |
476 ms |
20072 KB |
Output is correct |
36 |
Correct |
453 ms |
19760 KB |
Output is correct |
37 |
Correct |
441 ms |
20072 KB |
Output is correct |
38 |
Correct |
423 ms |
32212 KB |
Output is correct |
39 |
Correct |
392 ms |
26596 KB |
Output is correct |
40 |
Correct |
641 ms |
30544 KB |
Output is correct |
41 |
Correct |
413 ms |
23104 KB |
Output is correct |
42 |
Correct |
505 ms |
20844 KB |
Output is correct |
43 |
Correct |
477 ms |
21440 KB |
Output is correct |
44 |
Correct |
459 ms |
21472 KB |
Output is correct |
45 |
Correct |
535 ms |
21512 KB |
Output is correct |
46 |
Correct |
443 ms |
33232 KB |
Output is correct |
47 |
Correct |
497 ms |
27416 KB |
Output is correct |
48 |
Correct |
414 ms |
27360 KB |
Output is correct |
49 |
Correct |
414 ms |
30672 KB |
Output is correct |
50 |
Correct |
591 ms |
21424 KB |
Output is correct |
51 |
Correct |
594 ms |
21468 KB |
Output is correct |
52 |
Correct |
362 ms |
29920 KB |
Output is correct |
53 |
Correct |
357 ms |
29976 KB |
Output is correct |
54 |
Correct |
330 ms |
50108 KB |
Output is correct |
55 |
Correct |
337 ms |
45372 KB |
Output is correct |
56 |
Correct |
414 ms |
23024 KB |
Output is correct |
57 |
Correct |
383 ms |
28128 KB |
Output is correct |
58 |
Correct |
357 ms |
28204 KB |
Output is correct |
59 |
Correct |
374 ms |
30148 KB |
Output is correct |
60 |
Correct |
338 ms |
28400 KB |
Output is correct |
61 |
Correct |
359 ms |
29532 KB |
Output is correct |
62 |
Correct |
410 ms |
29380 KB |
Output is correct |
63 |
Correct |
485 ms |
29804 KB |
Output is correct |
64 |
Correct |
368 ms |
29024 KB |
Output is correct |
65 |
Correct |
345 ms |
29544 KB |
Output is correct |