fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6. //堀江伸一 会津大学オンラインジャッジ問3545 Zigzag Alignment 合格
  7. int red=0;
  8. int blue=1;
  9.  
  10. struct E{
  11. 	int color,r,height;
  12. };
  13. struct E2{
  14. 	int color;
  15. 	int commit;
  16. 	int len;
  17. 	int height;
  18. 	int no;
  19. 	int count;
  20. };
  21. struct E3{
  22. 	int right,commit,len;
  23. 	bool operator<(const E3& e3)const{
  24. 		if(right!=e3.right)return right<e3.right;
  25. 		if(commit!=e3.commit) return commit<e3.commit;
  26. 		return len<e3.len;
  27. 	}
  28. };
  29.  
  30. map<E3,long long int> perm;
  31. vector<E> vs;
  32. queue<E2> qs;
  33. int main() {
  34. 	int r1=1;
  35. 	int n,m;
  36. 	cin>>n>>m;
  37. 	for(int i=0;i<n;i++){
  38. 		E e1;
  39. 		cin>>e1.height;
  40. 		e1.color=red;
  41. 		e1.r=r1;
  42. 		vs.push_back(e1);
  43. 		r1*=2;
  44. 	}
  45. 	for(int i=0;i<m;i++){
  46. 		E e1;
  47. 		cin>>e1.height;
  48. 		e1.color=blue;
  49. 		e1.r=r1;
  50. 		vs.push_back(e1);
  51. 		r1*=2;
  52. 	}
  53. 	for(int i=0;i<vs.size();i++){
  54. 		E e1=vs[i];
  55. 		E2 e2;
  56. 		E3 e3;
  57. 		e3.right=i;
  58. 		e3.commit=e1.r;
  59. 		e3.len=1;
  60. 		perm[e3]=1;
  61. 		e2.color=e1.color;
  62. 		e2.commit=e1.r;
  63. 		e2.len=1;
  64. 		e2.height=e1.height;
  65. 		e2.no=i;
  66. 		e2.count=1;
  67. 		qs.push(e2);
  68. 	}
  69. 	long long int ans=0;
  70. 	while(qs.size()>0){
  71. 		E2 e2=qs.front();
  72. 		qs.pop();
  73. 		if(e2.count==n+m){
  74. 			if(1<e2.len){
  75. 				E3 e3;
  76. 				e3.right=e2.no;
  77. 				e3.commit=e2.commit;
  78. 				e3.len=e2.len;
  79. 				ans+=perm[e3];
  80. 				//cout<<e3.right<<" "<<e3.commit<<" "<<e2.len<<" "<<perm[e3]<<endl;
  81. 			}
  82. 			continue;
  83. 		}
  84.  
  85. 		for(int i=0;i<n+m;i++){
  86. 			E e1=vs[i];
  87. 			if((e2.commit & e1.r)>0)continue;
  88. 			E2 e2next;
  89. 			e2next.commit=e2.commit+e1.r;
  90. 			e2next.height=e1.height;
  91. 			e2next.color=e1.color;
  92. 			e2next.no=i;
  93. 			e2next.count=e2.count+1;
  94. 			E3 e3now,e3next;
  95. 			e3now.right=e2.no;
  96. 			e3now.commit=e2.commit;
  97. 			e3next.right=i;
  98. 			e3next.commit=e2next.commit;
  99.  
  100. 			if(e2.color==e1.color && e2.height<e1.height){
  101. 				e2next.len=e2.len+1;
  102. 				e3next.len=e2.len+1;
  103. 				e3now.len=e2.len;
  104. 				if(perm.find(e3next)==perm.end()){
  105. 					qs.push(e2next);
  106. 					perm[e3next]=0;
  107. 				}
  108. 				perm[e3next]+=perm[e3now];
  109. 			}else if(1<e2.len && e2.height>e1.height && e2.color!=e1.color){
  110. 				e2next.len=1;
  111. 				e3next.len=1;
  112. 				e3now.len=e2.len;
  113. 				if(perm.find(e3next)==perm.end()){
  114. 					qs.push(e2next);
  115. 					perm[e3next]=0;
  116. 				}
  117. 				perm[e3next]+=perm[e3now];
  118. 			}
  119. 		}
  120. 	}
  121. 	cout<<ans<<endl;
  122. 	return 0;
  123. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4 2
6 3 1 4
2 5
stdout
copy 
8
https://ideone.com/FD4juq
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

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!