#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e6 + 10 ;
int a[MAX] , b[MAX] ;
int n ;
int take_min[MAX] , take_max[MAX] , take_free[MAX] ;
int taken[MAX] ;
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < 2*n ; ++i)
cin>>a[i] ;
for(int i = 0 ; i < 2*n ; ++i)
cin>>b[i] ;
for(int i = 0 ; i < 2*n-1 ; ++i)
{
if(min(a[i] , b[i]) > max(a[i+1] , b[i+1]))
return cout<<-1<<"\n" , 0 ;
if(min(a[i] , b[i]) > min(a[i+1] , b[i+1]))
take_max[i+1] = 1 ;
else if(take_max[i] && max(a[i] , b[i]) > min(a[i+1] , b[i+1]))
take_max[i+1] = 1 ;
}
for(int i = 2*n-1 ; i > 0 ; --i)
{
if(max(a[i] , b[i]) < max(a[i-1] , b[i-1]))
take_min[i-1] = 1 ;
else if(take_min[i] && min(a[i] , b[i]) < max(a[i-1] , b[i-1]))
take_min[i-1] = 1 ;
}
for(int i = 0 ; i < 2*n ; ++i)
{
if(take_max[i] && take_min[i])
return cout<<-1<<"\n" , 0 ;
if(take_max[i] || take_min[i])
continue ;
take_free[i] = 1 ;
if(i-1 >= 0 && (min(a[i] , b[i]) < max(a[i-1] , b[i-1]) && !take_min[i-1]))
take_free[i] = 0 ;
if(i+1 < 2*n && (max(a[i] , b[i]) > min(a[i+1] , b[i+1]) && !take_max[i+1]))
take_free[i] = 0 ;
}
vector< vector< pair<int , int> > >vp ;
bool flag = false ;
int ans = 0 , cnt = 0 ;
for(int i = 0 ; i < 2*n ; ++i)
{
flag &= (!take_free[i] && !take_max[i] && !take_min[i]) ;
if(take_max[i])
{
if(a[i] > b[i])
ans++ , taken[i] = 0 ;
else
ans-- , taken[i] = 1 ;
}
else if(take_min[i])
{
if(a[i] < b[i])
ans++ , taken[i] = 0 ;
else
ans-- , taken[i] = 1 ;
}
else if(take_free[i])
cnt++ ;
else
{
if(!flag)
vp.push_back({}) ;
else
{
if(min(a[i] , b[i]) >= max(a[i-1] , b[i-1]))
vp.push_back({}) ;
}
if(a[i] > b[i])
ans++ , taken[i] = 0 , vp.back().emplace_back(-2 , i) ;
else
ans-- , taken[i] = 1 , vp.back().emplace_back(2 , i) ;
flag = true ;
}
}
for(auto &v2 : vp)
{
int Max = 0 , Min = 0 , sum = 0 ;
for(auto &p : v2)
{
sum += p.first ;
Max = max(Max , sum) , Min = min(Min , sum) ;
}
if(ans > 0)
{
int a = min(-1 * Min , ans) ;
if((a & 1))
a -= (a & 1) ;
ans -= a ;
sum = 0 ;
for(auto &p : v2)
{
if(-1 * sum == a)
break ;
taken[p.second] ^= 1 ;
sum += p.first ;
}
}
else
{
int a = min(Max , -1 * ans) ;
if((a & 1))
a -= (a & 1) ;
ans += a ;
sum = 0 ;
for(auto &p : v2)
{
if(sum == a)
break ;
taken[p.second] ^= 1 ;
sum += p.first ;
}
}
}
for(int i = 0 ; i < 2*n ; ++i)
{
if(take_free[i])
{
if(ans < 0)
taken[i] = 0 , ans++ ;
else
taken[i] = 1 , ans-- ;
}
}
if(ans != 0)
return cout<<-1<<"\n" , 0 ;
for(int i = 0 ; i < 2*n ; ++i)
cout<<(char)('A' + taken[i]) ;
cout<<"\n" ;
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
352 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
352 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
468 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
468 KB |
Output is correct |
34 |
Correct |
144 ms |
8072 KB |
Output is correct |
35 |
Correct |
177 ms |
19488 KB |
Output is correct |
36 |
Correct |
176 ms |
19144 KB |
Output is correct |
37 |
Correct |
180 ms |
19508 KB |
Output is correct |
38 |
Correct |
176 ms |
22500 KB |
Output is correct |
39 |
Correct |
205 ms |
38416 KB |
Output is correct |
40 |
Correct |
199 ms |
35352 KB |
Output is correct |
41 |
Correct |
172 ms |
23804 KB |
Output is correct |
42 |
Correct |
172 ms |
16588 KB |
Output is correct |
43 |
Correct |
192 ms |
20924 KB |
Output is correct |
44 |
Correct |
191 ms |
21108 KB |
Output is correct |
45 |
Correct |
215 ms |
20948 KB |
Output is correct |
46 |
Correct |
184 ms |
17088 KB |
Output is correct |
47 |
Correct |
210 ms |
42448 KB |
Output is correct |
48 |
Correct |
217 ms |
39532 KB |
Output is correct |
49 |
Correct |
228 ms |
35456 KB |
Output is correct |
50 |
Correct |
190 ms |
20968 KB |
Output is correct |
51 |
Correct |
197 ms |
20960 KB |
Output is correct |
52 |
Correct |
144 ms |
23396 KB |
Output is correct |
53 |
Correct |
165 ms |
23504 KB |
Output is correct |
54 |
Correct |
128 ms |
24092 KB |
Output is correct |
55 |
Correct |
132 ms |
24904 KB |
Output is correct |
56 |
Correct |
187 ms |
25072 KB |
Output is correct |
57 |
Correct |
152 ms |
21116 KB |
Output is correct |
58 |
Correct |
173 ms |
21400 KB |
Output is correct |
59 |
Correct |
173 ms |
26092 KB |
Output is correct |
60 |
Correct |
154 ms |
22384 KB |
Output is correct |
61 |
Correct |
171 ms |
23680 KB |
Output is correct |
62 |
Correct |
159 ms |
23840 KB |
Output is correct |
63 |
Correct |
163 ms |
24268 KB |
Output is correct |
64 |
Correct |
164 ms |
23208 KB |
Output is correct |
65 |
Correct |
163 ms |
24012 KB |
Output is correct |