Source code for submission s1154

fp.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <string>
  7. #include <deque>
  8. #include <list>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <stack>
  13. #include <vector>
  14. using namespace std;
  15.  
  16. //#define debug printf
  17. #define debug blackhole
  18. void blackhole(...) {}
  19.  
  20. #define NP 12
  21. int PENT[NP][25] = {
  22. {
  23. 0,0,0,0,0,
  24. 0,0,1,1,0,
  25. 0,1,1,0,0,
  26. 0,0,1,0,0,
  27. 0,0,0,0,0
  28. },
  29. {
  30. 0,0,1,0,0,
  31. 0,0,1,0,0,
  32. 0,0,1,0,0,
  33. 0,0,1,0,0,
  34. 0,0,1,0,0
  35. },
  36. {
  37. 0,0,1,0,0,
  38. 0,0,1,0,0,
  39. 0,0,1,0,0,
  40. 0,0,1,1,0,
  41. 0,0,0,0,0
  42. },
  43. {
  44. 0,0,0,1,0,
  45. 0,0,0,1,0,
  46. 0,0,1,1,0,
  47. 0,0,1,0,0,
  48. 0,0,0,0,0
  49. },
  50. {
  51. 0,0,1,1,0,
  52. 0,0,1,1,0,
  53. 0,0,1,0,0,
  54. 0,0,0,0,0,
  55. 0,0,0,0,0
  56. },
  57. {
  58. 0,0,0,0,0,
  59. 0,1,1,1,0,
  60. 0,0,1,0,0,
  61. 0,0,1,0,0,
  62. 0,0,0,0,0
  63. },
  64. {
  65. 0,0,0,0,0,
  66. 0,1,0,1,0,
  67. 0,1,1,1,0,
  68. 0,0,0,0,0,
  69. 0,0,0,0,0,
  70. },
  71. {
  72. 0,0,0,0,0,
  73. 0,1,0,0,0,
  74. 0,1,0,0,0,
  75. 0,1,1,1,0,
  76. 0,0,0,0,0,
  77. },
  78. {
  79. 0,0,0,0,0,
  80. 0,1,0,0,0,
  81. 0,1,1,0,0,
  82. 0,0,1,1,0,
  83. 0,0,0,0,0
  84. },
  85. {
  86. 0,0,0,0,0,
  87. 0,0,1,0,0,
  88. 0,1,1,1,0,
  89. 0,0,1,0,0,
  90. 0,0,0,0,0
  91. },
  92. {
  93. 0,0,0,0,0,
  94. 0,0,1,0,0,
  95. 0,1,1,0,0,
  96. 0,0,1,0,0,
  97. 0,0,1,0,0
  98. },
  99. {
  100. 0,0,0,0,0,
  101. 0,1,1,0,0,
  102. 0,0,1,0,0,
  103. 0,0,1,1,0,
  104. 0,0,0,0,0
  105. }
  106. };
  107.  
  108. int rnd[10][10][2];
  109.  
  110. int hash(int what[10][10]) {
  111. int h=4523;
  112. for (int i=0;i<10;i++) {
  113. for (int j=0;j<10;j++) {
  114. h ^= rnd[i][j][what[i][j] ? 1 : 0];
  115. }
  116. }
  117. return h;
  118. }
  119.  
  120. bool connected(int both[10][10]) {
  121. for (int i = 0; i < 10; i++) {
  122. for (int j = 0; j < 10; j++) {
  123. if (both[i][j] != 1) continue;
  124. if (j > 0 && both[i][j-1] == 2) return true;
  125. if (j < 9 && both[i][j+1] == 2) return true;
  126. if (i > 0 && both[i-1][j] == 2) return true;
  127. if (i < 9 && both[i+1][j] == 2) return true;
  128. }
  129. }
  130. return false;
  131. }
  132.  
  133. void make_pent(int res[5][5], int x) {
  134. for (int i = 0; i < 5; i++) {
  135. for (int j = 0; j < 5; j++) {
  136. res[i][j] = PENT[x][i * 5 + j];
  137. }
  138. }
  139. }
  140.  
  141. void dump(int res[5][5]) {
  142. for (int i=0;i<5;i++) {
  143. for (int j=0;j<5;j++) {
  144. debug("%c", res[i][j] ? 'X' : ' ');
  145. }
  146. debug("\n");
  147. }
  148. debug("\n");
  149. }
  150.  
  151. void rotate_pent(int res[5][5]) {
  152. int tmp[5][5];
  153. for (int i = 0; i < 5; i++) {
  154. for (int j = 0; j < 5; j++) {
  155. tmp[j][5 - i - 1] = res[i][j];
  156. }
  157. }
  158. for (int i = 0; i < 5; i++) {
  159. for (int j = 0; j < 5; j++) {
  160. res[i][j] = tmp[i][j];
  161. }
  162. }
  163. }
  164.  
  165. void flip_pent(int res[5][5]) {
  166. int tmp[5][5];
  167. for (int i = 0; i < 5; i++) {
  168. for (int j = 0; j < 5; j++) {
  169. tmp[5 - i - 1][j] = res[i][j];
  170. }
  171. }
  172. for (int i = 0; i < 5; i++) {
  173. for (int j = 0; j < 5; j++) {
  174. res[i][j] = tmp[i][j];
  175. }
  176. }
  177. }
  178.  
  179. bool make_both(int both[10][10], int A, int Arot, int Aflip, int B, int Brot, int Bflip, int dx, int dy) {
  180. int rA[5][5], rB[5][5];
  181. make_pent(rA, A); make_pent(rB, B);
  182. if (Aflip) flip_pent(rA);
  183. if (Bflip) flip_pent(rB);
  184. for (int r = 0; r < Arot; r++) rotate_pent(rA);
  185. for (int r = 0; r < Brot; r++) rotate_pent(rB);
  186.  
  187. for (int i=0;i<10;i++) for (int j=0;j<10;j++) both[i][j] = 0;
  188.  
  189. for (int i = 0; i < 5; i++) {
  190. for (int j = 0; j < 5; j++) {
  191. both[i][j] = rA[i][j] ? 1 : 0;
  192. }
  193. }
  194.  
  195. for (int i = 0; i < 5; i++) {
  196. for (int j = 0; j < 5; j++) {
  197. if (!rB[i][j]) continue;
  198. if (both[i+dx][j+dy]) return false;
  199. both[i][j] = 2;
  200. }
  201. }
  202.  
  203. if (!connected(both)) return false;
  204. return true;
  205. }
  206.  
  207. set<pair<int, pair<int, int> > > pairs;
  208.  
  209. void generate() {
  210. for (int A=0; A<NP;A++) {
  211. for (int B=A;B<NP;B++) {
  212. for (int Arot = 0; Arot < 4; Arot++) {
  213. for (int Brot = 0; Brot < 4; Brot++) {
  214. for (int Aflip=0;Aflip<2;Aflip++) {
  215. for (int Bflip=0;Bflip<2;Bflip++) {
  216. for (int dx=0;dx<=5;dx++) {
  217. for (int dy=0;dy<=5;dy++) {
  218. int both[10][10];
  219. if (!make_both(both, A, Arot, Aflip, B, Brot, Bflip, dx, dy)) continue;
  220. int h = hash(both);
  221.  
  222. pairs.insert(make_pair(h, make_pair(A,B)));
  223. }
  224. }}}
  225. }
  226. }
  227. }
  228. }
  229. }
  230.  
  231. int locate(char c) {
  232. char* names="FILNPTUVWXYZ";
  233. for (int i = 0; names[i]; i++) {
  234. if (names[i] == c) return i;
  235. }
  236. debug("ERROR!");
  237. exit(1);
  238. }
  239.  
  240. int main() {
  241. int res[5][5];
  242. make_pent(res, 5);
  243. dump(res);
  244. rotate_pent(res);
  245. dump(res);
  246. rotate_pent(res);
  247. dump(res);
  248. rotate_pent(res);
  249. dump(res);
  250. rotate_pent(res);
  251. dump(res);
  252. srand(0);
  253. for (int i=0;i<10;i++) {
  254. for (int j=0;j<10;j++) {
  255. for (int k=0;k<2;k++) {
  256. rnd[i][j][k] = rand();
  257. }
  258. }
  259. }
  260. generate();
  261.  
  262. // printf("%d\n", pairs.size());
  263. set<pair<pair<int, int>, pair<int,int> > > all_pairs;
  264. for (set<pair<int, pair<int,int> > >::iterator i = pairs.begin(); i != pairs.end(); i++) {
  265. int h = i->first;
  266. for (set<pair<int, pair<int,int> > >::iterator j = pairs.begin(); j != pairs.end(); j++) {
  267. if (j->first == h) {
  268. // debug("[(%d,%d) <=> (%d,%d)]\n", i->second.first, i->second.second, j->second.first, j->second.second);
  269. int a = i->second.first, b = i->second.second, x = j->second.first, y = j->second.second;
  270. all_pairs.insert(make_pair(make_pair(a, b), make_pair(x, y)));
  271. all_pairs.insert(make_pair(make_pair(a, b), make_pair(y, x)));
  272. all_pairs.insert(make_pair(make_pair(b, a), make_pair(x, y)));
  273. all_pairs.insert(make_pair(make_pair(b, a), make_pair(y, x)));
  274. }
  275. }
  276. }
  277. // printf("\n");
  278. while (true) {
  279. char A[10], B[10];
  280. if (scanf("%s%s", A, B) != 2) break;
  281. int Ai = locate(A[0]), Aj = locate(A[1]), Bi = locate(B[0]), Bj = locate(B[1]);
  282. debug("[%d %d] vs [%d %d]\n", Ai, Aj, Bi, Bj);
  283.  
  284. if (all_pairs.find(make_pair(make_pair(Ai,Aj),make_pair(Bi,Bj))) != all_pairs.end()) {
  285. printf("YES\n");
  286. } else {
  287. printf("NO\n");
  288. }
  289. }
  290.  
  291. return 0;
  292. }
  293.