#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
#define iii pair<ii, int>
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n; n *= 2;
vector<iii> arr;
for(int i = 0; i < n; i++){
int x;
cin >> x;
arr.pb({{x, i}, 1});
}
for(int i = 0; i < n; i++){
int x;
cin >> x;
arr.pb({{x, i}, -1});
}
sort(all(arr));
vector<int> L, R;
int l = 0;
for(int i = 0; i < n; i++){
while(l < sz(arr) && i != arr[l].first.second) l++;
if(l == sz(arr)){
cout << -1;
return 0;
}
L.pb(l);
}
int r = sz(arr) - 1;
for(int i = n - 1; i >= 0; i--){
while(i != arr[r].first.second) r--;
R.pb(r);
}
reverse(all(R));
vector<vector<int> > Lgrp, Rgrp;
vector<ii> range;
vector<int> tl, tr;
l = 0, r = 0;
while(l < sz(L) && r < sz(R)){
tl.clear(), tr.clear();
int sum = 0;
int mn, mx;
do{
if(l != sz(L) && (r == sz(R) || L[l] <= R[r])){
sum++;
tl.pb(L[l++]);
}
else{
sum--;
tr.pb(R[r++]);
}
}while(sz(tl) != sz(tr));
for(auto p : tl){
sum += arr[p].second;
}
mn = mx = sum;
for(int i = sz(tl) - 1; i >= 0; i--){
sum -= arr[tl[i]].second;
sum += arr[tr[i]].second;
mn = min(mn, sum);
mx = max(mx, sum);
}
Lgrp.pb(tl);
Rgrp.pb(tr);
range.pb({mn, mx});
}
vector<int> g;
int S = 0;
for(auto p : range) S += p.first, g.pb(p.first);
if(S > 0 || (S + INF) % 2){
cout << -1;
return 0;
}
l = 0;
for(int i = 0; i < sz(range); i++){
int c = min(range[i].second - range[i].first, -S);
S += c;
g[i] += c;
}
if(S < 0){
cout << -1;
return 0;
}
vector<int> ans(n);
for(int i = 0; i < sz(range); i++){
int sum = 0;
for(int j = sz(Lgrp[i]) - 1; j >= 0; j--){
ans[arr[Lgrp[i][j]].first.second] = arr[Lgrp[i][j]].second;
sum += arr[Lgrp[i][j]].second;
}
for(int j = sz(Lgrp[i]) - 1; j >= 0 && sum != g[i]; j--){
sum -= arr[Lgrp[i][j]].second;
sum += arr[Rgrp[i][j]].second;
ans[arr[Lgrp[i][j]].first.second] = arr[Rgrp[i][j]].second;
}
}
for(int i = 0; i < n; i++) cout << (ans[i] == 1 ? 'A' : 'B');
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
704 KB |
Output is correct |
6 |
Correct |
7 ms |
1088 KB |
Output is correct |
7 |
Correct |
7 ms |
1088 KB |
Output is correct |
8 |
Correct |
7 ms |
1216 KB |
Output is correct |
9 |
Correct |
6 ms |
832 KB |
Output is correct |
10 |
Correct |
6 ms |
704 KB |
Output is correct |
11 |
Correct |
7 ms |
1216 KB |
Output is correct |
12 |
Correct |
7 ms |
1216 KB |
Output is correct |
13 |
Correct |
7 ms |
1216 KB |
Output is correct |
14 |
Correct |
7 ms |
1216 KB |
Output is correct |
15 |
Correct |
7 ms |
960 KB |
Output is correct |
16 |
Correct |
6 ms |
832 KB |
Output is correct |
17 |
Correct |
7 ms |
960 KB |
Output is correct |
18 |
Correct |
7 ms |
1216 KB |
Output is correct |
19 |
Correct |
7 ms |
1216 KB |
Output is correct |
20 |
Correct |
7 ms |
1216 KB |
Output is correct |
21 |
Correct |
7 ms |
1216 KB |
Output is correct |
22 |
Correct |
7 ms |
1216 KB |
Output is correct |
23 |
Correct |
7 ms |
1216 KB |
Output is correct |
24 |
Correct |
6 ms |
704 KB |
Output is correct |
25 |
Correct |
6 ms |
960 KB |
Output is correct |
26 |
Correct |
6 ms |
960 KB |
Output is correct |
27 |
Correct |
6 ms |
704 KB |
Output is correct |
28 |
Correct |
6 ms |
960 KB |
Output is correct |
29 |
Correct |
6 ms |
960 KB |
Output is correct |
30 |
Correct |
6 ms |
960 KB |
Output is correct |
31 |
Correct |
6 ms |
960 KB |
Output is correct |
32 |
Correct |
6 ms |
960 KB |
Output is correct |
33 |
Correct |
7 ms |
1088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
704 KB |
Output is correct |
6 |
Correct |
7 ms |
1088 KB |
Output is correct |
7 |
Correct |
7 ms |
1088 KB |
Output is correct |
8 |
Correct |
7 ms |
1216 KB |
Output is correct |
9 |
Correct |
6 ms |
832 KB |
Output is correct |
10 |
Correct |
6 ms |
704 KB |
Output is correct |
11 |
Correct |
7 ms |
1216 KB |
Output is correct |
12 |
Correct |
7 ms |
1216 KB |
Output is correct |
13 |
Correct |
7 ms |
1216 KB |
Output is correct |
14 |
Correct |
7 ms |
1216 KB |
Output is correct |
15 |
Correct |
7 ms |
960 KB |
Output is correct |
16 |
Correct |
6 ms |
832 KB |
Output is correct |
17 |
Correct |
7 ms |
960 KB |
Output is correct |
18 |
Correct |
7 ms |
1216 KB |
Output is correct |
19 |
Correct |
7 ms |
1216 KB |
Output is correct |
20 |
Correct |
7 ms |
1216 KB |
Output is correct |
21 |
Correct |
7 ms |
1216 KB |
Output is correct |
22 |
Correct |
7 ms |
1216 KB |
Output is correct |
23 |
Correct |
7 ms |
1216 KB |
Output is correct |
24 |
Correct |
6 ms |
704 KB |
Output is correct |
25 |
Correct |
6 ms |
960 KB |
Output is correct |
26 |
Correct |
6 ms |
960 KB |
Output is correct |
27 |
Correct |
6 ms |
704 KB |
Output is correct |
28 |
Correct |
6 ms |
960 KB |
Output is correct |
29 |
Correct |
6 ms |
960 KB |
Output is correct |
30 |
Correct |
6 ms |
960 KB |
Output is correct |
31 |
Correct |
6 ms |
960 KB |
Output is correct |
32 |
Correct |
6 ms |
960 KB |
Output is correct |
33 |
Correct |
7 ms |
1088 KB |
Output is correct |
34 |
Correct |
548 ms |
49800 KB |
Output is correct |
35 |
Correct |
756 ms |
192888 KB |
Output is correct |
36 |
Correct |
733 ms |
190224 KB |
Output is correct |
37 |
Correct |
755 ms |
193656 KB |
Output is correct |
38 |
Correct |
711 ms |
193656 KB |
Output is correct |
39 |
Correct |
612 ms |
134648 KB |
Output is correct |
40 |
Correct |
657 ms |
140812 KB |
Output is correct |
41 |
Correct |
457 ms |
99060 KB |
Output is correct |
42 |
Correct |
682 ms |
200484 KB |
Output is correct |
43 |
Correct |
794 ms |
206212 KB |
Output is correct |
44 |
Correct |
784 ms |
206080 KB |
Output is correct |
45 |
Correct |
897 ms |
206112 KB |
Output is correct |
46 |
Correct |
907 ms |
206180 KB |
Output is correct |
47 |
Correct |
597 ms |
142968 KB |
Output is correct |
48 |
Correct |
660 ms |
142984 KB |
Output is correct |
49 |
Correct |
697 ms |
141300 KB |
Output is correct |
50 |
Correct |
772 ms |
206104 KB |
Output is correct |
51 |
Correct |
788 ms |
206072 KB |
Output is correct |
52 |
Correct |
689 ms |
206196 KB |
Output is correct |
53 |
Correct |
705 ms |
206200 KB |
Output is correct |
54 |
Correct |
731 ms |
206244 KB |
Output is correct |
55 |
Correct |
654 ms |
206164 KB |
Output is correct |
56 |
Correct |
790 ms |
110988 KB |
Output is correct |
57 |
Correct |
642 ms |
154488 KB |
Output is correct |
58 |
Correct |
717 ms |
155000 KB |
Output is correct |
59 |
Correct |
452 ms |
103672 KB |
Output is correct |
60 |
Correct |
646 ms |
141688 KB |
Output is correct |
61 |
Correct |
702 ms |
150752 KB |
Output is correct |
62 |
Correct |
644 ms |
148472 KB |
Output is correct |
63 |
Correct |
717 ms |
150548 KB |
Output is correct |
64 |
Correct |
651 ms |
145656 KB |
Output is correct |
65 |
Correct |
693 ms |
150820 KB |
Output is correct |