#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
const int inf=1e9;
int n,a[MAXN],b[MAXN],cnt,p[MAXN],l,r;
int dp[MAXN][2],dp2[MAXN][2];
bool li[MAXN][2],li2[MAXN][2];
queue<int> s;
string sol,sol2;
int ff(int pos,int last){
if(pos==n+1)return 0;
if(li[pos][last])return dp[pos][last];
li[pos][last]=true;
dp[pos][last]=-inf;
int x=0;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x){
dp[pos][last]=max(dp[pos][last],ff(pos+1,0)+1);
}
if(b[pos]>=x){
dp[pos][last]=max(dp[pos][last],ff(pos+1,1));
}
return dp[pos][last];
}
int ff2(int pos,int last){
if(pos==n+1)return 0;
if(li2[pos][last])return dp2[pos][last];
li2[pos][last]=true;
dp2[pos][last]=-inf;
int x=0;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x){
dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,0));
}
if(b[pos]>=x){
dp2[pos][last]=max(dp2[pos][last],ff2(pos+1,1)+1);
}
return dp2[pos][last];
}
void solve(int pos,int last){
if(pos==n+1)return;
int x;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(a[pos]>=x and ff(pos,last)==ff(pos+1,0)+1){
sol+="A"; solve(pos+1,0); return;
}else{
sol+="B"; solve(pos+1,1); return;
}
}
void solve2(int pos,int last){
if(pos==n+1)return;
int x;
if(last==0)x=a[pos-1];
else x=b[pos-1];
if(b[pos]>=x and ff2(pos,last)==ff2(pos+1,1)+1){
sol2+="B"; solve2(pos+1,1); return;
}else{
sol2+="A"; solve2(pos+1,0); return;
}
}
bool vis[MAXN];
void bfs(int pos){
if(pos>0 and !vis[pos-1] and sol[pos-1]=='A' and sol2[pos-1]=='B'){
l=pos-1;
if(b[l+1]>=p[l] and b[l+1]<=p[l+2]){
s.push(pos-1);
vis[pos-1]=true;
}
}
if(pos<n-1 and !vis[pos+1] and sol[pos+1]=='A' and sol2[pos+1]=='B'){
l=pos+1;
if(b[l+1]>=p[l] and b[l+1]<=p[l+2]){
s.push(pos+1);
vis[pos+1]=true;
}
}
if(pos>0 and !vis[pos-1] and sol[pos-1]=='B' and sol2[pos-1]=='A'){
l=pos-1;
if(a[l+1]>=p[l] and a[l+1]<=p[l+2]){
s.push(pos-1);
vis[pos-1]=true;
}
}
if(pos<n-1 and !vis[pos+1] and sol[pos+1]=='B' and sol2[pos+1]=='A'){
l=pos+1;
if(a[l+1]>=p[l] and a[l+1]<=p[l+2]){
s.push(pos+1);
vis[pos+1]=true;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
n*=2;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
if(ff(1,0)<0 or ff(1,0)<n/2 or ff2(1,0)<n/2){
cout<<"-1\n";
return 0;
}
cnt=ff(1,0);
solve(1,0); solve2(1,0);
for(int i=0;i<sol.size();i++){
if(sol[i]=='A')p[i+1]=a[i+1];
else p[i+1]=b[i+1];
}
p[n+1]=inf;
for(int i=0;i<sol.size();i++){
if(sol[i]=='A' and sol2[i]=='B'){
if(b[i+1]>=p[i] and b[i+1]<=p[i+2]){
s.push(i); vis[i]=true;
}
}
if(sol[i]=='B' and sol2[i]=='A'){
if(a[i+1]>=p[i] and a[i+1]<=p[i+2]){
s.push(i); vis[i]=true;
}
}
}
while(cnt>n/2 and !s.empty()){
if(sol[s.front()]=='A'){
sol[s.front()]='B'; cnt--;
p[s.front()+1]=b[s.front()+1];
}else{
sol[s.front()]='A'; cnt++;
p[s.front()+1]=a[s.front()+1];
}
bfs(s.front());
s.pop();
}
cout<<sol<<"\n";
return 0;
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:147:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
building4.cpp:153:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
12752 KB |
Output is correct |
5 |
Correct |
2 ms |
8792 KB |
Output is correct |
6 |
Correct |
4 ms |
13024 KB |
Output is correct |
7 |
Correct |
2 ms |
12888 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
13092 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
13096 KB |
Output is correct |
14 |
Correct |
3 ms |
13148 KB |
Output is correct |
15 |
Correct |
3 ms |
12904 KB |
Output is correct |
16 |
Correct |
2 ms |
10844 KB |
Output is correct |
17 |
Correct |
3 ms |
13092 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
4 ms |
13024 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
13028 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
13148 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
27 |
Correct |
3 ms |
13020 KB |
Output is correct |
28 |
Correct |
2 ms |
12892 KB |
Output is correct |
29 |
Correct |
3 ms |
13024 KB |
Output is correct |
30 |
Correct |
3 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
13020 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
12636 KB |
Output is correct |
4 |
Correct |
2 ms |
12752 KB |
Output is correct |
5 |
Correct |
2 ms |
8792 KB |
Output is correct |
6 |
Correct |
4 ms |
13024 KB |
Output is correct |
7 |
Correct |
2 ms |
12888 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
2 ms |
12892 KB |
Output is correct |
11 |
Correct |
3 ms |
13092 KB |
Output is correct |
12 |
Correct |
3 ms |
12892 KB |
Output is correct |
13 |
Correct |
3 ms |
13096 KB |
Output is correct |
14 |
Correct |
3 ms |
13148 KB |
Output is correct |
15 |
Correct |
3 ms |
12904 KB |
Output is correct |
16 |
Correct |
2 ms |
10844 KB |
Output is correct |
17 |
Correct |
3 ms |
13092 KB |
Output is correct |
18 |
Correct |
3 ms |
12892 KB |
Output is correct |
19 |
Correct |
3 ms |
12892 KB |
Output is correct |
20 |
Correct |
4 ms |
13024 KB |
Output is correct |
21 |
Correct |
3 ms |
12888 KB |
Output is correct |
22 |
Correct |
3 ms |
13028 KB |
Output is correct |
23 |
Correct |
3 ms |
12892 KB |
Output is correct |
24 |
Correct |
3 ms |
13148 KB |
Output is correct |
25 |
Correct |
3 ms |
12892 KB |
Output is correct |
26 |
Correct |
3 ms |
12892 KB |
Output is correct |
27 |
Correct |
3 ms |
13020 KB |
Output is correct |
28 |
Correct |
2 ms |
12892 KB |
Output is correct |
29 |
Correct |
3 ms |
13024 KB |
Output is correct |
30 |
Correct |
3 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
13020 KB |
Output is correct |
32 |
Correct |
3 ms |
12892 KB |
Output is correct |
33 |
Correct |
3 ms |
12892 KB |
Output is correct |
34 |
Correct |
153 ms |
32320 KB |
Output is correct |
35 |
Correct |
269 ms |
109876 KB |
Output is correct |
36 |
Correct |
272 ms |
108624 KB |
Output is correct |
37 |
Correct |
300 ms |
110548 KB |
Output is correct |
38 |
Correct |
269 ms |
114360 KB |
Output is correct |
39 |
Correct |
252 ms |
110900 KB |
Output is correct |
40 |
Correct |
269 ms |
117584 KB |
Output is correct |
41 |
Correct |
295 ms |
111544 KB |
Output is correct |
42 |
Correct |
294 ms |
113660 KB |
Output is correct |
43 |
Correct |
280 ms |
116812 KB |
Output is correct |
44 |
Correct |
291 ms |
116840 KB |
Output is correct |
45 |
Correct |
283 ms |
116932 KB |
Output is correct |
46 |
Correct |
271 ms |
120884 KB |
Output is correct |
47 |
Correct |
259 ms |
116816 KB |
Output is correct |
48 |
Correct |
265 ms |
116928 KB |
Output is correct |
49 |
Correct |
260 ms |
117792 KB |
Output is correct |
50 |
Correct |
286 ms |
115988 KB |
Output is correct |
51 |
Correct |
290 ms |
116156 KB |
Output is correct |
52 |
Correct |
228 ms |
105808 KB |
Output is correct |
53 |
Correct |
223 ms |
106056 KB |
Output is correct |
54 |
Correct |
230 ms |
102336 KB |
Output is correct |
55 |
Correct |
226 ms |
108080 KB |
Output is correct |
56 |
Correct |
320 ms |
116068 KB |
Output is correct |
57 |
Correct |
258 ms |
110928 KB |
Output is correct |
58 |
Correct |
262 ms |
111440 KB |
Output is correct |
59 |
Correct |
256 ms |
111156 KB |
Output is correct |
60 |
Correct |
240 ms |
106448 KB |
Output is correct |
61 |
Correct |
241 ms |
111968 KB |
Output is correct |
62 |
Correct |
233 ms |
110524 KB |
Output is correct |
63 |
Correct |
240 ms |
113336 KB |
Output is correct |
64 |
Correct |
264 ms |
110340 KB |
Output is correct |
65 |
Correct |
240 ms |
113404 KB |
Output is correct |