fork download 
  1. #include <bits/stdc++.h>
  2. #define fastio cin.tie(0)->sync_with_stdio(0)
  3. using namespace std;
  4.  
  5. constexpr int M = 7;
  6. constexpr int SZ = (1 << M) | 1;
  7. constexpr int HA = (1 << M - 1) | 1;
  8. unsigned char cache1[M - 1][HA][SZ][SZ];
  9. unsigned char cache2[M - 1][SZ][SZ][SZ];
  10.  
  11. int F(int n, int x1, int y1, int x2, int y2, int d = 0) {
  12. 	const int sz = 1 << n;
  13. 	if (x1 == x2 && y1 == y2) return 0;
  14. 	if (d == 1) { // rotate cw
  15. 		return F(n, y1, sz - x1, y2, sz - x2);
  16. 	}
  17. 	if (d == 2) { // rotate ccw
  18. 		return F(n, sz - y1, x1, sz - y2, x2);
  19. 	}
  20. 	if (n == 1) { // base case
  21. 		if (x1 == x2 && y1 > y2) swap(y1, y2);
  22. 		if (y1 == y2 && x1 > x2) swap(x1, x2);
  23. 		if (x1 == x2) {
  24. 			if (x1 == 1 && y1 == 0 && y2 >= 1) return 1;
  25. 			return 0;
  26. 		}
  27. 		else {
  28. 			if (y1 == 1) return x1 == 0 && x2 == 2 ? 2 : x1 == 0 || x2 == 2 ? 1 : 0;
  29. 			return 0;
  30. 		}
  31. 	}
  32. 	if (x1 == x2 && x1 > sz / 2) return F(n, sz - x1, y1, sz - x2, y2);
  33. 	else if (n <= M) {
  34. 		if (x1 == x2 && y1 > y2) swap(y1, y2);
  35. 		if (y1 == y2 && x1 > x2) swap(x1, x2);
  36. 		unsigned char& ret = x1 == x2 ? cache1[n - 2][x1][y1][y2] : cache2[n - 2][y1][x1][x2];
  37. 		if ((char)ret != -1) return ret;
  38. 		if (x1 == x2) {
  39. 			if (x1 == sz / 2) {
  40. 				return ret = y1 < sz / 2 && y2 >= sz / 2;
  41. 			}
  42. 			else {
  43. 				if (x1 < sz / 2) {
  44. 					if (y2 <= sz / 2) {
  45. 						return ret = F(n - 1, x1, y1, x2, y2);
  46. 					}
  47. 					else if (y1 >= sz / 2) {
  48. 						return ret = F(n - 1, x1, y1 - sz / 2, x2, y2 - sz / 2, 1);
  49. 					}
  50. 					else {
  51. 						return ret = F(n - 1, x1, y1, x2, sz / 2) + F(n - 1, x1, 0, x2, y2 - sz / 2, 1);
  52. 					}
  53. 				}
  54. 				else {
  55. 					if (y2 <= sz / 2) {
  56. 						return ret = F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, y2);
  57. 					}
  58. 					else if (y1 >= sz / 2) {
  59. 						return ret = F(n - 1, x1 - sz / 2, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  60. 					}
  61. 					else {
  62. 						return ret = F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, sz / 2) + F(n - 1, x1 - sz / 2, 0, x2 - sz / 2, y2 - sz / 2, 2);
  63. 					}
  64. 				}
  65. 			}
  66. 		}
  67. 		else {
  68. 			if (y1 == sz / 2) {
  69. 				return ret = (int)(x1 == 0) + (int)(x2 == sz);
  70. 			}
  71. 			else {
  72. 				if (y1 < sz / 2) {
  73. 					if (x2 <= sz / 2) {
  74. 						return ret = F(n - 1, x1, y1, x2, y2);
  75. 					}
  76. 					else if (x1 >= sz / 2) {
  77. 						return ret = F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, y2);
  78. 					}
  79. 					else {
  80. 						return ret = F(n - 1, x1, y1, sz / 2, y2) + F(n - 1, 0, y1, x2 - sz / 2, y2);
  81. 					}
  82. 				}
  83. 				else {
  84. 					if (x2 <= sz / 2) {
  85. 						return ret = F(n - 1, x1, y1 - sz / 2, x2, y2 - sz / 2, 1);
  86. 					}
  87. 					else if (x1 >= sz / 2) {
  88. 						return ret = F(n - 1, x1 - sz / 2, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  89. 					}
  90. 					else {
  91. 						return ret = F(n - 1, x1, y1 - sz / 2, sz / 2, y2 - sz / 2, 1) + F(n - 1, 0, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  92. 					}
  93. 				}
  94. 			}
  95. 		}
  96. 	}
  97. 	else { // divide and conquer
  98. 		if (x1 == x2 && y1 > y2) swap(y1, y2);
  99. 		if (y1 == y2 && x1 > x2) swap(x1, x2);
  100. 		if (x1 == x2) {
  101. 			if (x1 == sz / 2) {
  102. 				return y1 < sz / 2 && y2 >= sz / 2;
  103. 			}
  104. 			else {
  105. 				if (x1 < sz / 2) {
  106. 					if (y2 <= sz / 2) {
  107. 						return F(n - 1, x1, y1, x2, y2);
  108. 					}
  109. 					else if (y1 >= sz / 2) {
  110. 						return F(n - 1, x1, y1 - sz / 2, x2, y2 - sz / 2, 1);
  111. 					}
  112. 					else {
  113. 						return F(n - 1, x1, y1, x2, sz / 2) + F(n - 1, x1, 0, x2, y2 - sz / 2, 1);
  114. 					}
  115. 				}
  116. 				else {
  117. 					if (y2 <= sz / 2) {
  118. 						return F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, y2);
  119. 					}
  120. 					else if (y1 >= sz / 2) {
  121. 						return F(n - 1, x1 - sz / 2, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  122. 					}
  123. 					else {
  124. 						return F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, sz / 2) + F(n - 1, x1 - sz / 2, 0, x2 - sz / 2, y2 - sz / 2, 2);
  125. 					}
  126. 				}
  127. 			}
  128. 		}
  129. 		else {
  130. 			if (y1 == sz / 2) {
  131. 				return (int)(x1 == 0) + (int)(x2 == sz);
  132. 			}
  133. 			else {
  134. 				if (y1 < sz / 2) {
  135. 					if (x2 <= sz / 2) {
  136. 						return F(n - 1, x1, y1, x2, y2);
  137. 					}
  138. 					else if (x1 >= sz / 2) {
  139. 						return F(n - 1, x1 - sz / 2, y1, x2 - sz / 2, y2);
  140. 					}
  141. 					else {
  142. 						return F(n - 1, x1, y1, sz / 2, y2) + F(n - 1, 0, y1, x2 - sz / 2, y2);
  143. 					}
  144. 				}
  145. 				else {
  146. 					if (x2 <= sz / 2) {
  147. 						return F(n - 1, x1, y1 - sz / 2, x2, y2 - sz / 2, 1);
  148. 					}
  149. 					else if (x1 >= sz / 2) {
  150. 						return F(n - 1, x1 - sz / 2, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  151. 					}
  152. 					else {
  153. 						return F(n - 1, x1, y1 - sz / 2, sz / 2, y2 - sz / 2, 1) + F(n - 1, 0, y1 - sz / 2, x2 - sz / 2, y2 - sz / 2, 2);
  154. 					}
  155. 				}
  156. 			}
  157. 		}
  158. 	}
  159. }
  160.  
  161. int main() {
  162. 	fastio;
  163. 	memset(cache1, -1, sizeof cache1);
  164. 	memset(cache2, -1, sizeof cache2);
  165. 	for (int n, x1, x2, y; cin >> n && n;) {
  166. 		cin >> x1 >> x2 >> y;
  167. 		cout << F(n, x1, y, x2, y) << '\n';
  168. 	}
  169. }
Success #stdin #stdout 4.82s 22388KB
comments (?)
stdin 
30 0 1073741824 1
30 0 1073741824 2
30 0 1073741824 3
30 0 1073741824 4
30 0 1073741824 5
30 0 1073741824 6
30 0 1073741824 7
30 0 1073741824 8
30 0 1073741824 9
30 0 1073741824 10
30 0 1073741824 11
30 0 1073741824 12
30 0 1073741824 13
30 0 1073741824 14
30 0 1073741824 15
30 0 1073741824 16
30 0 1073741824 17
30 0 1073741824 18
30 0 1073741824 19
30 0 1073741824 20
30 0 1073741824 21
30 0 1073741824 22
30 0 1073741824 23
30 0 1073741824 24
30 0 1073741824 25
30 0 1073741824 26
30 0 1073741824 27
30 0 1073741824 28
30 0 1073741824 29
30 0 1073741824 30
30 0 1073741824 31
30 0 1073741824 32
30 0 1073741824 33
30 0 1073741824 34
30 0 1073741824 35
30 0 1073741824 36
30 0 1073741824 37
30 0 1073741824 38
30 0 1073741824 39
30 0 1073741824 40
30 0 1073741824 41
30 0 1073741824 42
30 0 1073741824 43
30 0 1073741824 44
30 0 1073741824 45
30 0 1073741824 46
30 0 1073741824 47
30 0 1073741824 48
30 0 1073741824 49
30 0 1073741824 50
0
stdout 
1073741824
536870912
536870912
268435456
805306368
268435456
805306368
134217728
671088640
402653184
939524096
134217728
939524096
402653184
671088640
67108864
738197504
335544320
872415232
201326592
738197504
469762048
872415232
67108864
872415232
469762048
738197504
201326592
872415232
335544320
738197504
33554432
704643072
369098752
905969664
167772160
838860800
436207616
771751936
100663296
838860800
369098752
771751936
234881024
704643072
436207616
905969664
33554432
905969664
436207616
https://ideone.com/BV0vFV
language:
C++14 (gcc 8.3)
created:
2 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!