fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef  long long llo;
  6. #define mp make_pair
  7. #define pb push_back
  8. #define a first
  9. #define b second
  10. #define endl "\n"
  11. int main(){
  12. 	ios_base::sync_with_stdio(false);
  13. 	cin.tie(NULL);
  14. 	int n;
  15. 	cin>>n;
  16. 	int aa[2*n];
  17. 	int bb[2*n];
  18. 	for(int i=0;i<2*n;i++){
  19. 		cin>>aa[i];
  20. 	}	
  21. 	for(int i=0;i<2*n;i++){
  22. 		cin>>bb[i];
  23. 	}
  24. 	pair<int,int> dp[2*n][2];
  25. 	dp[0][0]={1,1};
  26. 	dp[0][1]={0,0};
  27. 	for(int i=1;i<2*n;i++){
  28. 		int st=0;
  29. 		dp[i][0]={-1,-1};
  30. 		dp[i][1]={-1,-1};
  31. 		if(aa[i]>=aa[i-1]){
  32. 			if(dp[i-1][0].a!=-1){
  33. 				dp[i][0]={dp[i-1][0].a+1,dp[i-1][0].b+1};
  34. 				st=1;
  35. 			}
  36. 		}
  37. 		if(aa[i]>=bb[i-1]){
  38. 			if(dp[i-1][1].a!=-1){
  39. 				if(st==0){
  40. 					dp[i][0]={dp[i-1][1].a+1,dp[i-1][1].b+1};
  41. 					st=1;
  42. 				}
  43. 				else{
  44. 					dp[i][0].a=min(dp[i][0].a,dp[i-1][1].a+1);
  45. 					dp[i][0].b=max(dp[i][0].b,dp[i-1][1].b+1);
  46. 					st=1;
  47. 				}
  48. 			}
  49. 		}
  50.  
  51. 		int stt=0;
  52. 		if(bb[i]>=aa[i-1]){
  53. 			if(dp[i-1][0].a!=-1){
  54. 				dp[i][1]=dp[i-1][0];
  55.  
  56. 				stt=1;
  57. 			}
  58. 		}
  59. 		if(bb[i]>=bb[i-1]){
  60. 			if(dp[i-1][1].a!=-1){
  61. 				if(stt==0){
  62. 					dp[i][1]=dp[i-1][1];
  63. 				}
  64. 				else{
  65. 					dp[i][1].a=min(dp[i][1].a,dp[i-1][1].a);
  66. 					dp[i][1].b=max(dp[i][1].b,dp[i-1][1].b);
  67. 				}
  68. 			}
  69. 		}
  70. 	}
  71. 	int ans[2*n];
  72. 	int so=-1;
  73.  
  74. 	if(dp[2*n-1][0].a<=n and dp[2*n-1][0].b>=n){
  75. 		so=0;
  76. 	}
  77. 	if(dp[2*n-1][1].a<=n and dp[2*n-1][1].b>=n){
  78. 		so=1;
  79. 	}
  80.  
  81. 	if(so==-1){
  82. 		cout<<-1;
  83. 		return 0;
  84. 	}
  85. 	ans[2*n-1]=so;
  86. 	int co=n-(1-so);
  87.  
  88. 	for(int i=2*n-2;i>=0;i--){
  89. 		int soo;
  90. 		int x=aa[i+1];
  91. 		if(ans[i+1]==1){
  92. 			x=bb[i+1];
  93. 		}
  94. 		if( dp[i][0].a<=co and dp[i][0].b>=co and aa[i]<=x and co>0){
  95. 			soo=0;
  96. 			co-=1;
  97. 		}
  98. 		else if(dp[i][1].a<=co and dp[i][1].b>=co and bb[i]<=x){
  99. 			soo=1;
  100. 		}
  101. 		ans[i]=soo;
  102. 	}
  103. 	for(int i=0;i<2*n;i++){
  104. 		if(ans[i]==0){
  105. 			cout<<"A";
  106. 		}
  107. 		else{
  108. 			cout<<"B";
  109. 		}
  110. 	}
  111.  
  112.  
  113.  
  114.  
  115. 	return 0;
  116. }
  117.  
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
2
1 4 10 20
3 5 8 13
stdout
copy 
BAAB
https://ideone.com/1xsqh1
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!