#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1000006)
ll n,A[2][MAXN];
bool ans[MAXN],block[MAXN];
int main(){
FAST
cin>>n;
n*=2;
FOR(j,0,1)FOR(i,1,n)cin>>A[j][i];
ans[1]=(A[0][1]<A[1][1]?0:1);
FOR(i,2,n){
if((A[0][i]<A[1][i]&&A[0][i]>=A[ans[i-1]][i-1])||(A[1][i]<A[ans[i-1]][i-1])){
ans[i]=0;
}else ans[i]=1;
if(A[ans[i]][i]<A[ans[i-1]][i-1]){
cout<<"-1\n";
return 0;
}
}
vector<ll> cnt(2,0);
FOR(i,1,n)++cnt[ans[i]];
FOR(i,1,n){
if(cnt[0]==cnt[1])break;
if(cnt[ans[i]]<cnt[!ans[i]])continue;
if(A[!ans[i]][i]<A[ans[i]][i])continue;
if(block[i])continue;
ll cur=1, p=A[!ans[i]][i], j=i+1;
bool gg=0;
while(j<=n){
if(A[ans[j]][j]>=p) break;
if(A[!ans[j]][j]<p) { FOR(k,i,j-1) block[k]=1; gg=1; break; }
if(cnt[ans[j]]>cnt[!ans[j]]) ++ cur;
else -- cur;
if(cur<0){FOR(k,i,j)block[k]=1;gg=1;break;}
// if(cnt[!ans[i]]+cur>cnt[ans[i]]-cur){
// gg=1;break;
// }
p=A[!ans[j]][j];
++ j;
} // j is where we cannot reach
if(gg){
continue;
}
if(cnt[!ans[i]]+cur>cnt[ans[i]]-cur){
ll start=-1;
FOR(k,i,j-1) {
if(cnt[ans[k]]>cnt[!ans[k]]) -- cur; else ++ cur;
if(cnt[!ans[i]]+cur==cnt[ans[i]]-cur){
start=k+1;
}
}
assert(~start);
FOR(k,start,j-1)--cnt[ans[k]],ans[k]^=1,++cnt[ans[k]];
i=j-1;
continue;
}
// flip
FOR(k,i,j-1)--cnt[ans[k]],ans[k]^=1,++cnt[ans[k]];
i=j-1;
}
if(cnt[0]==cnt[1]){
FOR(i,1,n)cout<<(ans[i]?'B':'A');
cout<<'\n';
}else cout<<"-1\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 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 |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
6 ms |
384 KB |
Output is correct |
12 |
Correct |
6 ms |
384 KB |
Output is correct |
13 |
Correct |
6 ms |
384 KB |
Output is correct |
14 |
Correct |
6 ms |
384 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
6 ms |
384 KB |
Output is correct |
19 |
Correct |
6 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
432 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
512 KB |
Output is correct |
26 |
Correct |
6 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 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 |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
6 ms |
384 KB |
Output is correct |
12 |
Correct |
6 ms |
384 KB |
Output is correct |
13 |
Correct |
6 ms |
384 KB |
Output is correct |
14 |
Correct |
6 ms |
384 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
6 ms |
384 KB |
Output is correct |
19 |
Correct |
6 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
432 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
512 KB |
Output is correct |
26 |
Correct |
6 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |
34 |
Correct |
261 ms |
15620 KB |
Output is correct |
35 |
Correct |
274 ms |
16760 KB |
Output is correct |
36 |
Correct |
288 ms |
16664 KB |
Output is correct |
37 |
Correct |
293 ms |
16888 KB |
Output is correct |
38 |
Correct |
284 ms |
16888 KB |
Output is correct |
39 |
Correct |
275 ms |
17912 KB |
Output is correct |
40 |
Correct |
284 ms |
18040 KB |
Output is correct |
41 |
Correct |
292 ms |
17144 KB |
Output is correct |
42 |
Correct |
304 ms |
17400 KB |
Output is correct |
43 |
Correct |
321 ms |
18168 KB |
Output is correct |
44 |
Correct |
333 ms |
18276 KB |
Output is correct |
45 |
Correct |
351 ms |
18400 KB |
Output is correct |
46 |
Correct |
361 ms |
18040 KB |
Output is correct |
47 |
Correct |
358 ms |
18984 KB |
Output is correct |
48 |
Correct |
346 ms |
18936 KB |
Output is correct |
49 |
Correct |
304 ms |
18284 KB |
Output is correct |
50 |
Correct |
311 ms |
18936 KB |
Output is correct |
51 |
Correct |
318 ms |
18028 KB |
Output is correct |
52 |
Correct |
201 ms |
18428 KB |
Output is correct |
53 |
Correct |
212 ms |
18452 KB |
Output is correct |
54 |
Correct |
176 ms |
18424 KB |
Output is correct |
55 |
Correct |
197 ms |
18680 KB |
Output is correct |
56 |
Correct |
318 ms |
18172 KB |
Output is correct |
57 |
Correct |
251 ms |
18128 KB |
Output is correct |
58 |
Correct |
266 ms |
18296 KB |
Output is correct |
59 |
Correct |
272 ms |
18040 KB |
Output is correct |
60 |
Correct |
245 ms |
17784 KB |
Output is correct |
61 |
Correct |
281 ms |
18812 KB |
Output is correct |
62 |
Correct |
267 ms |
18556 KB |
Output is correct |
63 |
Correct |
274 ms |
18808 KB |
Output is correct |
64 |
Correct |
253 ms |
18168 KB |
Output is correct |
65 |
Correct |
284 ms |
18808 KB |
Output is correct |