#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define fi first
#define se second
#define pii pair<int,int>
const int maxn=5e5+10;
int n,a[2*maxn],b[2*maxn];
int L[2*maxn][3],R[2*maxn][3];
vector<char> kq;
bool chq(int u,int l,int r)
{
return u>=l&&u<=r;
}
main()
{
//freopen("test.inp","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
forinc(i,1,2*n) cin>>a[i];
forinc(i,1,2*n) cin>>b[i];
forinc(i,1,2*n+5) forinc(j,0,1) L[i][j]=INT_MAX;
forinc(i,1,2*n+5) forinc(j,0,1) R[i][j]=INT_MIN;
L[1][0]=0,L[1][1]=1;
R[1][0]=0,R[1][1]=1;
forinc(i,2,2*n) forinc(t,0,1)
{
if(t==0){
if(L[i-1][0]!=INT_MAX&&a[i]>=a[i-1]) L[i][t]=min(L[i][t],L[i-1][0]);
if(L[i-1][1]!=INT_MAX&&a[i]>=b[i-1]) L[i][t]=min(L[i][t],L[i-1][1]);
if(R[i-1][0]!=INT_MIN&&a[i]>=a[i-1]) R[i][t]=max(R[i][t],R[i-1][0]);
if(R[i-1][1]!=INT_MIN&&a[i]>=b[i-1]) R[i][t]=max(R[i][t],R[i-1][1]);
}
else{
if(L[i-1][0]!=INT_MAX&&b[i]>=a[i-1]) L[i][t]=min(L[i][t],L[i-1][0]+1);
if(L[i-1][1]!=INT_MAX&&b[i]>=b[i-1]) L[i][t]=min(L[i][t],L[i-1][1]+1);
if(R[i-1][0]!=INT_MIN&&b[i]>=a[i-1]) R[i][t]=max(R[i][t],R[i-1][0]+1);
if(R[i-1][1]!=INT_MIN&&b[i]>=b[i-1]) R[i][t]=max(R[i][t],R[i-1][1]+1);
}
}
if(!chq(n,L[2*n][0],R[2*n][0])&&!chq(n,L[2*n][1],R[2*n][1])) return cout<<-1,0;
int c=(chq(n,L[2*n][0],R[2*n][0])?0:1);
kq.push_back((char)('A'+c));
int cur=(c==0?n:n-1);
// cout<<L[5][1]<<" "<<R[5][1];
// return 0;
fordec(i,2*n-1,1)
{
bool ok=0;
if(chq(cur,L[i][0],R[i][0]))
{
int tmp=(c==0?a[i+1]:b[i+1]);
if(a[i]<=tmp)
{
// cout<<i<<" "<<1<<"\n";
kq.push_back('A');
c=0;
ok=1;
}
}
if(chq(cur,L[i][1],R[i][1])&&ok==0){
int tmp=(c==0?a[i+1]:b[i+1]);
// cout<<i;
// return 0;
if(b[i]<=tmp)
{
// cout<<i<<" "<<2<<"\n";
kq.push_back('B');
c=1;
cur--;
}
}
}
reverse(kq.begin(),kq.end());
for(auto &v:kq) cout<<v;
}
Compilation message
building4.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
7 ms |
640 KB |
Output is correct |
10 |
Correct |
7 ms |
640 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
768 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
6 ms |
640 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
6 ms |
768 KB |
Output is correct |
18 |
Correct |
6 ms |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
6 ms |
640 KB |
Output is correct |
21 |
Correct |
6 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
640 KB |
Output is correct |
23 |
Correct |
5 ms |
640 KB |
Output is correct |
24 |
Correct |
7 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
640 KB |
Output is correct |
26 |
Correct |
6 ms |
640 KB |
Output is correct |
27 |
Correct |
5 ms |
640 KB |
Output is correct |
28 |
Correct |
6 ms |
640 KB |
Output is correct |
29 |
Correct |
6 ms |
640 KB |
Output is correct |
30 |
Correct |
6 ms |
640 KB |
Output is correct |
31 |
Correct |
6 ms |
640 KB |
Output is correct |
32 |
Correct |
5 ms |
640 KB |
Output is correct |
33 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
7 ms |
640 KB |
Output is correct |
10 |
Correct |
7 ms |
640 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
768 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
6 ms |
640 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
6 ms |
768 KB |
Output is correct |
18 |
Correct |
6 ms |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
6 ms |
640 KB |
Output is correct |
21 |
Correct |
6 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
640 KB |
Output is correct |
23 |
Correct |
5 ms |
640 KB |
Output is correct |
24 |
Correct |
7 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
640 KB |
Output is correct |
26 |
Correct |
6 ms |
640 KB |
Output is correct |
27 |
Correct |
5 ms |
640 KB |
Output is correct |
28 |
Correct |
6 ms |
640 KB |
Output is correct |
29 |
Correct |
6 ms |
640 KB |
Output is correct |
30 |
Correct |
6 ms |
640 KB |
Output is correct |
31 |
Correct |
6 ms |
640 KB |
Output is correct |
32 |
Correct |
5 ms |
640 KB |
Output is correct |
33 |
Correct |
6 ms |
640 KB |
Output is correct |
34 |
Correct |
331 ms |
65400 KB |
Output is correct |
35 |
Correct |
362 ms |
78320 KB |
Output is correct |
36 |
Correct |
372 ms |
77040 KB |
Output is correct |
37 |
Correct |
404 ms |
78704 KB |
Output is correct |
38 |
Correct |
363 ms |
78588 KB |
Output is correct |
39 |
Correct |
342 ms |
63724 KB |
Output is correct |
40 |
Correct |
366 ms |
68468 KB |
Output is correct |
41 |
Correct |
366 ms |
79596 KB |
Output is correct |
42 |
Correct |
378 ms |
71532 KB |
Output is correct |
43 |
Correct |
401 ms |
83952 KB |
Output is correct |
44 |
Correct |
408 ms |
84588 KB |
Output is correct |
45 |
Correct |
367 ms |
66284 KB |
Output is correct |
46 |
Correct |
401 ms |
84332 KB |
Output is correct |
47 |
Correct |
389 ms |
83568 KB |
Output is correct |
48 |
Correct |
388 ms |
83440 KB |
Output is correct |
49 |
Correct |
419 ms |
84204 KB |
Output is correct |
50 |
Correct |
399 ms |
81520 KB |
Output is correct |
51 |
Correct |
392 ms |
82108 KB |
Output is correct |
52 |
Correct |
258 ms |
72672 KB |
Output is correct |
53 |
Correct |
258 ms |
72712 KB |
Output is correct |
54 |
Correct |
248 ms |
72176 KB |
Output is correct |
55 |
Correct |
247 ms |
72560 KB |
Output is correct |
56 |
Correct |
366 ms |
67948 KB |
Output is correct |
57 |
Correct |
327 ms |
79340 KB |
Output is correct |
58 |
Correct |
344 ms |
79600 KB |
Output is correct |
59 |
Correct |
340 ms |
79652 KB |
Output is correct |
60 |
Correct |
316 ms |
75116 KB |
Output is correct |
61 |
Correct |
344 ms |
80044 KB |
Output is correct |
62 |
Correct |
333 ms |
79068 KB |
Output is correct |
63 |
Correct |
354 ms |
79984 KB |
Output is correct |
64 |
Correct |
342 ms |
77036 KB |
Output is correct |
65 |
Correct |
348 ms |
79856 KB |
Output is correct |