/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;
const int N=2e6+7;
int l[N],n,c,a,b,x[N],y[N],mn[N],mx[N],k,t[N],m[N],inf=1e9+7,d1[N],d2[N],mark[N];
char ans[N];
vector<int>v1[N],v2[N];
queue<pair<int,pair<int,int>>>st;
int main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<2*n;i++)cin>>x[i];
x[2*n]=1e9;
for(int i=0;i<2*n;i++)cin>>y[i];
y[2*n]=1e9;
int u=2*n;
for(int i=0;i<2*n;i++){
int p=x[i+1],q=y[i+1];
if(x[i]<=p){
v1[i].pb(i+1);d1[i]++;
v2[i+1].pb(i);d2[i+1]++;
}
if(x[i]<=q){
v1[i].pb(i+1+u);d1[i]++;
v2[i+1+u].pb(i);d2[i+1+u]++;
}
if(y[i]<=p){
v1[i+u].pb(i+1);d1[i+u]++;
v2[i+1].pb(i+u);d2[i+1]++;
}
if(y[i]<=q){
v1[i+u].pb(i+1+u);d1[i+u]++;
v2[i+1+u].pb(i+u);d2[i+1+u]++;
}
}
for(int i=0;i<4*n;i++){
if(i%u!=2*n-1) st.push(mk(d1[i],mk(i,1)));
if(i%u!=0)st.push(mk(d2[i],mk(i,2)));
}
//cout<<d1[1]<<" "<<d2[1]<<endl;
while(st.size()){
int i=st.front().S.F,val=st.front().F,ff=st.front().S.S;
st.pop();
if(mark[i]) continue;
if(ff==1){
if(d1[i]!=val || val>0) continue;
}
else{
if(d2[i]!=val || val>0) continue;
}
//cout<<i<<endl;
mark[i]=1;
if(mark[i%u] && mark[i%u+u]){
cout<<-1;
return 0;
}
//cout<<i<<endl;
for(auto y:v1[i]){
if(!mark[y]){
//st.erase(mk(d2[y],mk(y,2)));
d2[y]--;
st.push(mk(d2[y],mk(y,2)));
}
}
for(auto y:v2[i]){
if(!mark[y]){
//st.erase(mk(d1[y],mk(y,1)));
d1[y]--;
st.push(mk(d1[y],mk(y,1)));
}
}
}
for(int i=0;i<2*n;i++){
if(mark[i])x[i]=inf;
if(mark[i+u])y[i]=inf;
if(x[i]==inf && y[i]==inf){
cout<<-1;
return 0;
}
else if(x[i]!=inf && y[i]!=inf){
if(max(x[i],y[i])<=min(x[i+1],y[i+1])){
c++;
}
else{
m[i]=1;
//cout<<i<<endl;
}
}
else if(x[i]!=inf || y[i]!=inf){
if(x[i]==inf){
b++;
//cout<<i<<endl;
}
else{
a++;
}
}
}
//cout<<a<<" "<<b<< " "<<c<<endl;
string s;
int M=0;
for(int i=0;i<2*n;){
if(!m[i]){
i++;
continue;
}
s="";
int f=0;
while(m[i]){
if(x[i]>y[i]){
s+='A';
f++;
}
else{
s+='B';
}
i++;
}
if(x[i]!=inf && y[i]!=inf){
if(i<2*n) c--;
if(x[i]>y[i]){
s+='A';
f++;
}
else{
s+='B';
}
i++;
}
mn[k]=f;mx[k]=f;
for(auto w:s){
if(w=='A'){
f--;
}
else{
f++;
}
mn[k]=min(mn[k],f);
mx[k]=max(mx[k],f);
}
M+=mn[k];
t[k]=mn[k];
k++;
}
if(M>n-a){
cout<<-1;
return 0;
}
int r=n-a-c;
for(int i=0;i<k;i++){
while(M<r && t[i]<mx[i]){
M++;
t[i]++;
}
}
if(M<r){
cout<<-1;
return 0;
}
fill(ans,ans+N,'f');
int g=0;
for(int i=0;i<2*n;){
if(!m[i]){
i++;
continue;
}
int h=i;
s="";
int f=0;
while(m[i]){
if(x[i]>y[i]){
s+='A';
f++;
}
else{
s+='B';
}
i++;
}
if(x[i]!=inf && y[i]!=inf){
if(x[i]>y[i]){
s+='A';
f++;
}
else{
s+='B';
}
i++;
}
string z;
if(f==t[g]){
z=s;
}
for(int j=0;j<s.size();j++){
char w=s[j];
if(w=='A'){
f--;
s[j]='B';
}
else{
f++;
s[j]='A';
}
if(f==t[g]){
z=s;
break;
}
}
a+=t[g];
for(int j=h;j<i;j++){
ans[j]=z[j-h];
}
g++;
}
for(int i=0;i<2*n;i++){
//cout<<ans[i];
}
//cout<<endl;
for(int i=0;i<2*n;i++){
if(ans[i]!='f') continue;
if(x[i]!=inf && y[i]!=inf){
if(a<n){
ans[i]='A';
a++;
}
else{
ans[i]='B';
}
}
else if(x[i]!=inf || y[i]!=inf){
if(x[i]==inf){
ans[i]='B';
}
else{
ans[i]='A';
}
}
}
int e=0;
for(int i=0;i<2*n;i++){
if(ans[i]=='A')l[i]=x[i];
else l[i]=y[i];
if(i!=0 && l[i]<l[i-1]){
e=1;
}
}
if(e){
cout<<-1;
return 0;
}
for(int i=0;i<2*n;i++){
cout<<ans[i];
}
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:207:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int j=0;j<s.size();j++){
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
96148 KB |
Output is correct |
2 |
Correct |
42 ms |
94168 KB |
Output is correct |
3 |
Correct |
43 ms |
96276 KB |
Output is correct |
4 |
Correct |
44 ms |
96176 KB |
Output is correct |
5 |
Correct |
47 ms |
94940 KB |
Output is correct |
6 |
Correct |
50 ms |
97056 KB |
Output is correct |
7 |
Correct |
45 ms |
96876 KB |
Output is correct |
8 |
Correct |
45 ms |
96988 KB |
Output is correct |
9 |
Correct |
49 ms |
96940 KB |
Output is correct |
10 |
Correct |
45 ms |
96900 KB |
Output is correct |
11 |
Correct |
50 ms |
96988 KB |
Output is correct |
12 |
Correct |
54 ms |
97012 KB |
Output is correct |
13 |
Correct |
46 ms |
97052 KB |
Output is correct |
14 |
Correct |
48 ms |
97028 KB |
Output is correct |
15 |
Correct |
47 ms |
97076 KB |
Output is correct |
16 |
Correct |
50 ms |
95144 KB |
Output is correct |
17 |
Correct |
46 ms |
97096 KB |
Output is correct |
18 |
Correct |
47 ms |
97104 KB |
Output is correct |
19 |
Correct |
47 ms |
96988 KB |
Output is correct |
20 |
Correct |
52 ms |
96936 KB |
Output is correct |
21 |
Correct |
50 ms |
97172 KB |
Output is correct |
22 |
Correct |
49 ms |
97076 KB |
Output is correct |
23 |
Correct |
46 ms |
97100 KB |
Output is correct |
24 |
Correct |
45 ms |
97056 KB |
Output is correct |
25 |
Correct |
45 ms |
97100 KB |
Output is correct |
26 |
Correct |
53 ms |
97028 KB |
Output is correct |
27 |
Correct |
46 ms |
97064 KB |
Output is correct |
28 |
Correct |
46 ms |
96992 KB |
Output is correct |
29 |
Correct |
46 ms |
97164 KB |
Output is correct |
30 |
Correct |
46 ms |
97172 KB |
Output is correct |
31 |
Correct |
45 ms |
97100 KB |
Output is correct |
32 |
Correct |
46 ms |
96940 KB |
Output is correct |
33 |
Correct |
46 ms |
97156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
96148 KB |
Output is correct |
2 |
Correct |
42 ms |
94168 KB |
Output is correct |
3 |
Correct |
43 ms |
96276 KB |
Output is correct |
4 |
Correct |
44 ms |
96176 KB |
Output is correct |
5 |
Correct |
47 ms |
94940 KB |
Output is correct |
6 |
Correct |
50 ms |
97056 KB |
Output is correct |
7 |
Correct |
45 ms |
96876 KB |
Output is correct |
8 |
Correct |
45 ms |
96988 KB |
Output is correct |
9 |
Correct |
49 ms |
96940 KB |
Output is correct |
10 |
Correct |
45 ms |
96900 KB |
Output is correct |
11 |
Correct |
50 ms |
96988 KB |
Output is correct |
12 |
Correct |
54 ms |
97012 KB |
Output is correct |
13 |
Correct |
46 ms |
97052 KB |
Output is correct |
14 |
Correct |
48 ms |
97028 KB |
Output is correct |
15 |
Correct |
47 ms |
97076 KB |
Output is correct |
16 |
Correct |
50 ms |
95144 KB |
Output is correct |
17 |
Correct |
46 ms |
97096 KB |
Output is correct |
18 |
Correct |
47 ms |
97104 KB |
Output is correct |
19 |
Correct |
47 ms |
96988 KB |
Output is correct |
20 |
Correct |
52 ms |
96936 KB |
Output is correct |
21 |
Correct |
50 ms |
97172 KB |
Output is correct |
22 |
Correct |
49 ms |
97076 KB |
Output is correct |
23 |
Correct |
46 ms |
97100 KB |
Output is correct |
24 |
Correct |
45 ms |
97056 KB |
Output is correct |
25 |
Correct |
45 ms |
97100 KB |
Output is correct |
26 |
Correct |
53 ms |
97028 KB |
Output is correct |
27 |
Correct |
46 ms |
97064 KB |
Output is correct |
28 |
Correct |
46 ms |
96992 KB |
Output is correct |
29 |
Correct |
46 ms |
97164 KB |
Output is correct |
30 |
Correct |
46 ms |
97172 KB |
Output is correct |
31 |
Correct |
45 ms |
97100 KB |
Output is correct |
32 |
Correct |
46 ms |
96940 KB |
Output is correct |
33 |
Correct |
46 ms |
97156 KB |
Output is correct |
34 |
Correct |
476 ms |
270216 KB |
Output is correct |
35 |
Correct |
623 ms |
289548 KB |
Output is correct |
36 |
Correct |
660 ms |
284580 KB |
Output is correct |
37 |
Correct |
636 ms |
289108 KB |
Output is correct |
38 |
Correct |
573 ms |
312628 KB |
Output is correct |
39 |
Correct |
551 ms |
292136 KB |
Output is correct |
40 |
Correct |
618 ms |
321056 KB |
Output is correct |
41 |
Correct |
500 ms |
309788 KB |
Output is correct |
42 |
Correct |
550 ms |
288196 KB |
Output is correct |
43 |
Correct |
683 ms |
304804 KB |
Output is correct |
44 |
Correct |
706 ms |
304836 KB |
Output is correct |
45 |
Correct |
669 ms |
304676 KB |
Output is correct |
46 |
Correct |
587 ms |
317608 KB |
Output is correct |
47 |
Correct |
653 ms |
306036 KB |
Output is correct |
48 |
Correct |
571 ms |
305916 KB |
Output is correct |
49 |
Correct |
638 ms |
309336 KB |
Output is correct |
50 |
Correct |
689 ms |
300688 KB |
Output is correct |
51 |
Correct |
667 ms |
303184 KB |
Output is correct |
52 |
Correct |
642 ms |
294528 KB |
Output is correct |
53 |
Correct |
638 ms |
292560 KB |
Output is correct |
54 |
Correct |
551 ms |
312700 KB |
Output is correct |
55 |
Correct |
550 ms |
294892 KB |
Output is correct |
56 |
Correct |
529 ms |
321860 KB |
Output is correct |
57 |
Correct |
520 ms |
315912 KB |
Output is correct |
58 |
Correct |
528 ms |
316936 KB |
Output is correct |
59 |
Correct |
505 ms |
316860 KB |
Output is correct |
60 |
Correct |
557 ms |
303000 KB |
Output is correct |
61 |
Correct |
596 ms |
318320 KB |
Output is correct |
62 |
Correct |
594 ms |
305336 KB |
Output is correct |
63 |
Correct |
641 ms |
308352 KB |
Output is correct |
64 |
Correct |
639 ms |
301452 KB |
Output is correct |
65 |
Correct |
608 ms |
318512 KB |
Output is correct |