Source code for submission s873

Go to diff to previous submission

fp.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28.  
  29. inline int two(int n) { return 1 << n; }
  30.  
  31. inline int shift(int n, int b)
  32. {
  33. if (b >= 0) return n << b;
  34. else return n >> (-b);
  35. }
  36.  
  37. inline int last_bit(int n)
  38. {
  39. return n&(-n);
  40. }
  41. ///////////////////////////////////////////////////////////////////////////
  42.  
  43. string pots[12][5] =
  44. {
  45. //F
  46. {
  47. ".##..",
  48. "##...",
  49. ".#...",
  50. ".....",
  51. ".....",
  52. },
  53.  
  54. //I
  55. {
  56. "#....",
  57. "#....",
  58. "#....",
  59. "#....",
  60. "#....",
  61. },
  62.  
  63. //L
  64. {
  65. "#....",
  66. "#....",
  67. "#....",
  68. "##...",
  69. ".....",
  70. },
  71.  
  72. // N
  73. {
  74. ".#...",
  75. ".#...",
  76. "##...",
  77. "#....",
  78. ".....",
  79. },
  80.  
  81. //P
  82. {
  83. "##...",
  84. "##...",
  85. "#....",
  86. ".....",
  87. ".....",
  88. },
  89.  
  90. //T
  91. {
  92. "###..",
  93. ".#...",
  94. ".#...",
  95. ".....",
  96. ".....",
  97. },
  98.  
  99. //U
  100. {
  101. "#.#..",
  102. "###..",
  103. ".....",
  104. ".....",
  105. ".....",
  106. },
  107.  
  108. //V
  109. {
  110. "#....",
  111. "#....",
  112. "###..",
  113. ".....",
  114. ".....",
  115. },
  116.  
  117. //W
  118. {
  119. "#....",
  120. "##...",
  121. ".##..",
  122. ".....",
  123. ".....",
  124. },
  125.  
  126. //X
  127. {
  128. ".#...",
  129. "###..",
  130. ".#...",
  131. ".....",
  132. ".....",
  133. },
  134.  
  135. //Y
  136. {
  137. ".#...",
  138. "##...",
  139. ".#...",
  140. ".#...",
  141. ".....",
  142. },
  143.  
  144. //Z
  145. {
  146. "##...",
  147. ".#...",
  148. ".##..",
  149. ".....",
  150. ".....",
  151. }
  152. };
  153.  
  154. void flip(vector<string> & from, vector<string> & to)
  155. {
  156. REP(i, 5) REP(j, 5)
  157. to[i][j] = from[i][4-j];
  158. }
  159.  
  160. void rot(vector<string> & from, vector<string> & to)
  161. {
  162. REP(i, 5) REP(j, 5)
  163. to[i][j] = from[4-j][i];
  164. }
  165.  
  166.  
  167. int shapes[12][8][5];
  168.  
  169. void init()
  170. {
  171. REP(i, 12)
  172. {
  173. vector<string> from(5), to(5, string(5, '.'));
  174. REP(j, 5) from[j] = pots[i][j];
  175.  
  176. int ind = 0;
  177. REP(f, 2)
  178. {
  179. REP(r, 4)
  180. {
  181. rot(from ,to);
  182. from = to;
  183.  
  184. REP(j, 5)
  185. {
  186. shapes[i][ind][j] = 0;
  187. REP(k, 5)
  188. if (from[j][k] == '#')
  189. shapes[i][ind][j] ^= two(k);
  190. }
  191.  
  192. ++ind;
  193. }
  194. flip(from, to);
  195. from = to;
  196. }
  197. }
  198. }
  199.  
  200.  
  201. string letters = "FILNPTUVWXYZ";
  202. char in[10];
  203.  
  204. int get_index(char c)
  205. {
  206. REP(i, letters.size())
  207. if (c == letters[i])
  208. return i;
  209. return -1;
  210. }
  211.  
  212. const int MAXX = 7, MAXY = 7, MASKY = (1<<MAXY)-1;
  213. int board[MAXX], board2[MAXY];
  214.  
  215. bool can(int x, int y, int * shape, int * board, int * board2=NULL)
  216. {
  217. REP(i, 5)
  218. {
  219. if (!shape[i]) continue; // nothing
  220. if (x+i < 0 || x+i >= MAXX) return false; // bad row
  221. if (!shift(last_bit(shape[i]), y)) return false; // bad left col
  222. int s = shift(shape[i], y);
  223. if ((s&MASKY) != s) return false; // bad right col
  224. if (board[x+i]&s) return false; // overlap
  225.  
  226. if (board2 != NULL && (board2[x+i]&s) != s) return false; // not matched
  227. }
  228. return true;
  229. }
  230.  
  231. void place(int x, int y, int * shape, int * board)
  232. {
  233. REP(i, 5)
  234. board[x+i] ^= shift(shape[i], y);
  235. }
  236.  
  237. int a1, a2, b1, b2;
  238.  
  239. bool place1();
  240. bool place2();
  241. bool place3();
  242. bool place4();
  243. }
  244.  
  245. bool place1()
  246. {
  247. FOR(x, -4, MAXX-1) FOR(y, -4, MAXY-1)
  248. if (can(x, y, shapes[a1][0], board))
  249. {
  250. place(x, y, shapes[a1][0], board);
  251. if (place2()) return true;
  252. place(x, y, shapes[a1][0], board);
  253. }
  254. return false;
  255. }
  256.  
  257. bool place2()
  258. {
  259. FOR(x, -4, MAXX-1) FOR(y, -4, MAXY-1) REP(s, 8)
  260. if (can(x, y, shapes[a2][s], board))
  261. {
  262. place(x, y, shapes[a2][s], board);
  263. if (place3()) return true;
  264. place(x, y, shapes[a2][s], board);
  265. }
  266. return false;
  267. }
  268.  
  269. bool place3()
  270. {
  271. FOR(x, -4, MAXX-1) FOR(y, -4, MAXY-1) REP(s, 8)
  272. if (can(x, y, shapes[b1][s], board2, board))
  273. {
  274. place(x, y, shapes[b1][s], board2);
  275. if (place4()) return true;
  276. place(x, y, shapes[b1][s], board2);
  277. }
  278. return false;
  279. }
  280.  
  281. bool place4()
  282. {
  283. FOR(x, -4, MAXX-1) FOR(y, -4, MAXY-1) REP(s, 8)
  284. if (can(x, y, shapes[b2][s], board2, board))
  285. return true;
  286. return false;
  287. }
  288.  
  289. int main()
  290. {
  291. init();
  292.  
  293. while (gets(in))
  294. {
  295. memset(board, 0, sizeof(board));
  296. memset(board2, 0, sizeof(board2));
  297. a1 = get_index(in[0]), a2 = get_index(in[1]), b1 = get_index(in[3]), b2 = get_index(in[4]);
  298. if (place1()) printf("YES\n");
  299. else printf("NO\n");
  300. }
  301.  
  302. return 0;
  303. }

Diff to submission s871

fp.cpp

--- c5.s871.cteam040.fp.cpp.0.fp.cpp
+++ c5.s873.cteam040.fp.cpp.0.fp.cpp
@@ -210,5 +210,5 @@
 }
 
-const int MAXX = 8, MAXY = 8, MASKY = (1<<MAXY)-1;
+const int MAXX = 7, MAXY = 7, MASKY = (1<<MAXY)-1;
 int board[MAXX], board2[MAXY];
 
@@ -241,4 +241,5 @@
 bool place3();
 bool place4();
+  }
 
 bool place1()