#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e6+99,S=2,inf=1e9+9;
int n,t,a[N][S],L[N][2],R[N][2],seg[N<<2][S];
string ans;
void solve(int id,int x,int nxt){
if(id==0) return ;
f(i,0,S){
if(a[id][i]<=nxt && L[id][i]<=x && x<=R[id][i]){
ans+=char('A'+i);
solve(id-1,x-i,a[id][i]);
return ;
}
}
assert(0);
}
int main(){
cin>>n; n<<=1;
f(i,1,n+1) cin>>a[i][0];
f(i,1,n+1) cin>>a[i][1];
L[1][0]=R[1][0]=0;
L[1][1]=R[1][1]=1;
f(i,2,n+1){
L[i][0]=L[i][1]=N;
R[i][0]=R[i][1]=-N;
f(p,0,S){
f(k,0,S){
if(a[i-1][p]>a[i][k]) continue ;
minm(L[i][k],L[i-1][p]+k);
maxm(R[i][k],R[i-1][p]+k);
}
}
}
f(i,0,S){
if(L[n][i]<=n/2 && n/2<=R[n][i]) break;
if(i==1){
return cout<<-1,0;
}
}
solve(n,n/2,inf);
reverse(all(ans));
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
3 ms |
332 KB |
Output is correct |
14 |
Correct |
3 ms |
332 KB |
Output is correct |
15 |
Correct |
4 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
440 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
4 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
332 KB |
Output is correct |
29 |
Correct |
3 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
324 KB |
Output is correct |
32 |
Correct |
2 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
3 ms |
332 KB |
Output is correct |
14 |
Correct |
3 ms |
332 KB |
Output is correct |
15 |
Correct |
4 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
440 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
25 |
Correct |
3 ms |
332 KB |
Output is correct |
26 |
Correct |
4 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
332 KB |
Output is correct |
29 |
Correct |
3 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
324 KB |
Output is correct |
32 |
Correct |
2 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
746 ms |
37400 KB |
Output is correct |
35 |
Correct |
682 ms |
42036 KB |
Output is correct |
36 |
Correct |
672 ms |
41468 KB |
Output is correct |
37 |
Correct |
690 ms |
42204 KB |
Output is correct |
38 |
Correct |
669 ms |
42072 KB |
Output is correct |
39 |
Correct |
956 ms |
41328 KB |
Output is correct |
40 |
Correct |
725 ms |
44788 KB |
Output is correct |
41 |
Correct |
660 ms |
42260 KB |
Output is correct |
42 |
Correct |
697 ms |
43788 KB |
Output is correct |
43 |
Correct |
740 ms |
45236 KB |
Output is correct |
44 |
Correct |
789 ms |
45200 KB |
Output is correct |
45 |
Correct |
750 ms |
45480 KB |
Output is correct |
46 |
Correct |
738 ms |
45144 KB |
Output is correct |
47 |
Correct |
696 ms |
44456 KB |
Output is correct |
48 |
Correct |
730 ms |
44220 KB |
Output is correct |
49 |
Correct |
718 ms |
44976 KB |
Output is correct |
50 |
Correct |
725 ms |
44460 KB |
Output is correct |
51 |
Correct |
704 ms |
44384 KB |
Output is correct |
52 |
Correct |
393 ms |
33424 KB |
Output is correct |
53 |
Correct |
393 ms |
33524 KB |
Output is correct |
54 |
Correct |
385 ms |
33440 KB |
Output is correct |
55 |
Correct |
378 ms |
33208 KB |
Output is correct |
56 |
Correct |
733 ms |
45356 KB |
Output is correct |
57 |
Correct |
596 ms |
40440 KB |
Output is correct |
58 |
Correct |
591 ms |
40712 KB |
Output is correct |
59 |
Correct |
602 ms |
40368 KB |
Output is correct |
60 |
Correct |
563 ms |
38404 KB |
Output is correct |
61 |
Correct |
594 ms |
40872 KB |
Output is correct |
62 |
Correct |
586 ms |
40352 KB |
Output is correct |
63 |
Correct |
594 ms |
40880 KB |
Output is correct |
64 |
Correct |
618 ms |
39564 KB |
Output is correct |
65 |
Correct |
678 ms |
40920 KB |
Output is correct |