Source code for submission s1013

Go to diff to previous submission

fp_pre.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.  
  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. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29. struct Tile{
  30. 	char arr[5][5];
  31. };
  32.  
  33. struct Bigtile{
  34. 	char arr[15][15];
  35. };
  36.  
  37. Tile tiles[12][8];
  38.  
  39. char help[28];
  40.  
  41. Tile reflect(const Tile& A){
  42. 	Tile B;
  43. 	REP(i,5) REP(j,5) B.arr[4-i][j] = A.arr[i][j];
  44. 	return B;
  45. }
  46.  
  47. Tile rotate(const Tile& A){
  48. 	Tile B;
  49. 	REP(i,5) REP(j,5) B.arr[4-j][i] = A.arr[i][j];
  50. 	return B;
  51. }
  52.  
  53. Bigtile reflect(const Bigtile& A){
  54. 	Bigtile B;
  55. 	REP(i,15) REP(j,15) B.arr[14-i][j] = A.arr[i][j];
  56. 	return B;
  57. }
  58.  
  59. Bigtile rotate(const Bigtile& A){
  60. 	Bigtile B;
  61. 	REP(i,15) REP(j,15) B.arr[14-j][i] = A.arr[i][j];
  62. 	return B;
  63. }
  64.  
  65. int charnum(char c){
  66. 	if(c=='F') return 0;
  67. 	if(c=='I') return 1;
  68. 	if(c=='L') return 2;
  69. 	if(c=='N') return 3;
  70. 	if(c=='P') return 4;
  71. 	if(c=='T') return 5;
  72. 	if(c=='U') return 6;
  73. 	if(c=='V') return 7;
  74. 	if(c=='W') return 8;
  75. 	if(c=='X') return 9;
  76. 	if(c=='Y') return 10;
  77. 	if(c=='Z') return 11; 
  78. 	return 0;
  79. }
  80.  
  81. Bigtile zero, Xzero,X;
  82. Bigtile shift(const Bigtile& A){
  83. 	Bigtile C = zero;
  84. 	int minX=20, minY=20;
  85. 	REP(i,15)REP(j,15){
  86. 		if (A.arr[i][j] == 'x') {
  87. 			if (i < minY) minY = i;
  88. 			if (j < minX) minX = j;
  89. 		}
  90. 	}
  91. 	if (minX == 20) return A;
  92. 	REP(i,15-minY)REP(j,15-minX){
  93. 		C.arr[i][j] = A.arr[i+minY][j+minX];
  94. 	}
  95. 	return C;
  96. }
  97.  
  98. bool compare(const Bigtile& A, const Bigtile& B){
  99. 	REP(i,15) REP(j,15){
  100. 		if(A.arr[i][j]!=B.arr[i][j]) return false;
  101. 		}
  102. 	return true;
  103. }
  104.  
  105. Bigtile con;
  106.  
  107. void dfs(int x, int y){
  108. 	if(x<0 || y<0 || x>=15 || y>=15) return;
  109. 	if(con.arr[x][y]=='.') return;
  110. 	con.arr[x][y]='.';
  111. 	dfs(x+1,y);
  112. 	dfs(x-1,y);
  113. 	dfs(x,y+1);
  114. 	dfs(x,y-1);
  115. }
  116. bool is_connected(){
  117. 	REP(i,15) REP(j,15){
  118. 		if(con.arr[i][j]=='x'){
  119. 			dfs(i,j);
  120. 			REP(k,15) REP(l,15) if(con.arr[k][l]=='x') return false;
  121. 			return true;
  122. 		}
  123. 	}
  124. 	return true;
  125. }
  126.  
  127.  
  128. vector< Bigtile > pos[12][12];
  129.  
  130. char c1,c2,c3,c4,c5,c6;
  131. bool done[12][12];
  132. int d1,d2,d3,d4;
  133. bool ok;
  134.  
  135. int main() {
  136. 	strcpy(help,".xx..xx....x.............");
  137. 	REP(i,5) REP(j,5) tiles[0][0].arr[i][j] = help[i*5+j];
  138.  
  139. 	strcpy(help,"x....x....x....x....x....");
  140. 	REP(i,5) REP(j,5) tiles[1][0].arr[i][j] = help[i*5+j];
  141.  
  142. 	strcpy(help,"x....x....x....xx........");
  143. 	REP(i,5) REP(j,5) tiles[2][0].arr[i][j] = help[i*5+j];
  144.  
  145. 	strcpy(help,".x....x...xx...x.........");
  146. 	REP(i,5) REP(j,5) tiles[3][0].arr[i][j] = help[i*5+j];
  147.  
  148. 	strcpy(help,"xx...xx...x..............");
  149. 	REP(i,5) REP(j,5) tiles[4][0].arr[i][j] = help[i*5+j];
  150.  
  151. 	strcpy(help,"xxx...x....x.............");
  152. 	REP(i,5) REP(j,5) tiles[5][0].arr[i][j] = help[i*5+j];
  153.  
  154. 	strcpy(help,"x.x..xxx.................");
  155. 	REP(i,5) REP(j,5) tiles[6][0].arr[i][j] = help[i*5+j];
  156.  
  157. 	strcpy(help,"x....x....xxx............");
  158. 	REP(i,5) REP(j,5) tiles[7][0].arr[i][j] = help[i*5+j];
  159.  
  160. 	strcpy(help,"x....xx....xx............");
  161. 	REP(i,5) REP(j,5) tiles[8][0].arr[i][j] = help[i*5+j];
  162.  
  163. 	strcpy(help,".x...xxx...x.............");
  164. 	REP(i,5) REP(j,5) tiles[9][0].arr[i][j] = help[i*5+j];
  165.  
  166. 	strcpy(help,".x...xx....x....x........");
  167. 	REP(i,5) REP(j,5) tiles[10][0].arr[i][j] = help[i*5+j];
  168.  
  169. 	strcpy(help,"xx....x....xx............");
  170. 	REP(i,5) REP(j,5) tiles[11][0].arr[i][j] = help[i*5+j];
  171.  
  172. 	REP(i,12){
  173. 		tiles[i][1] = reflect(tiles[i][0]);
  174. 		REP(j,3){
  175. 			tiles[i][2*j+2] = rotate(tiles[i][2*j]);
  176. 			tiles[i][2*j+3] = rotate(tiles[i][2*j+1]);
  177. 		}
  178. 	}
  179.  
  180. 	REP(i,15) REP(j,15) zero.arr[i][j]='.';
  181. 	while(scanf("%c%c %c%c\n",&c1,&c2,&c3,&c4) == 4){
  182. 		//DEBUG(c1);
  183. 		d1 = charnum(c1);
  184. 		d2 = charnum(c2);
  185. 		d3 = charnum(c3);
  186. 		d4 = charnum(c4);
  187. 		if (d1 > d2) swap(d1, d2);
  188. 		if (d3 > d4) swap(d3, d4);
  189. 		DEBUG(d1);
  190. 		DEBUG(d2);
  191. 		DEBUG(d3);
  192. 		DEBUG(d4);
  193. 		if(!done[d1][d2]){
  194. 			Xzero = zero;
  195. 			REP(k,8){
  196. 				REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j];
  197. 				REP(m,10) REP(n,10){
  198. 					ok=true;
  199. 					X = Xzero;
  200. 					REP(i,5) REP(j,5){
  201. 						if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false;
  202. 						if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j];
  203. 					}
  204. 					con = X;
  205. 					if(ok && is_connected()){
  206. 						REP(rot,4){
  207. 							pos[d1][d2].push_back(shift(X));
  208. 							pos[d1][d2].push_back(shift(reflect(X)));
  209. 							X = rotate(X);
  210. 						}
  211. 					}
  212. 				}
  213. 			}
  214.  
  215. 			REP(i,(int)pos[d1][d2].size()) {
  216. 				FOR(j,i+1,(int)pos[d1][d2].size()-1) {
  217. 					if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
  218. 						pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
  219. 						pos[d1][d2].pop_back();
  220. 						--j;
  221. 					}
  222. 				}
  223. 			}
  224. 			done[d1][d2] = true;
  225. 		}
  226.  
  227. 		if(!done[d3][d4]){
  228. 			d1 = d3; d2 = d4;
  229. 			Xzero = zero;
  230. 			REP(k,8){
  231. 				REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j];
  232. 				REP(m,10) REP(n,10){
  233. 					ok=true;
  234. 					X = Xzero;
  235. 					REP(i,5) REP(j,5){
  236. 						if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false;
  237. 						if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j];
  238. 					}
  239. 					con = X;
  240. 					if(ok && is_connected()){
  241. 						REP(rot,4){
  242. 							pos[d1][d2].push_back(shift(X));
  243. 							pos[d1][d2].push_back(shift(reflect(X)));
  244. 							X = rotate(X);
  245. 						}
  246. 					}
  247. 				}
  248. 			}
  249. 			REP(i,(int)pos[d1][d2].size()) {
  250. 				FOR(j,i+1,(int)pos[d1][d2].size()-1) {
  251. 					if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
  252. 						pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
  253. 						pos[d1][d2].pop_back();
  254. 						--j;
  255. 					}
  256. 				}
  257. 			}
  258. 			done[d1][d2] = true;
  259. 		}
  260. 		d1 = charnum(c1); d2 = charnum(c2);
  261. 		if(d1>d2) swap(d1,d2);
  262.  
  263. 		ok=false;
  264. 		REP(i,pos[d1][d2].size()){
  265. 			if(ok) break;
  266. 			REP(j,pos[d3][d4].size()){
  267. 				if(ok) break;
  268. 				if(compare(pos[d1][d2][i],pos[d3][d4][j])) ok=true;
  269. 			}
  270. 		}
  271.  
  272. 		printf("%s\n", ok ? "YES" : "NO");
  273. 	}
  274.  
  275. 	return 0;
  276. }
  277.  

Diff to submission s992

fp_pre.cpp

--- c5.s992.cteam010.fp.cpp.0.fp_pre.cpp
+++ c5.s1013.cteam010.fp.cpp.0.fp_pre.cpp
@@ -185,8 +185,10 @@
                 d3 = charnum(c3);
                 d4 = charnum(c4);
-                //DEBUG(d1);
-                //DEBUG(d2);
-                //DEBUG(d3);
-                //DEBUG(d4);
+                if (d1 > d2) swap(d1, d2);
+                if (d3 > d4) swap(d3, d4);
+                DEBUG(d1);
+                DEBUG(d2);
+                DEBUG(d3);
+                DEBUG(d4);
                 if(!done[d1][d2]){
                         Xzero = zero;
@@ -211,13 +213,14 @@
                         }
 
-                }
-                REP(i,(int)pos[d1][d2].size()) {
-                        FOR(j,i+1,(int)pos[d1][d2].size()-1) {
-                                if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
-                                        pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
-                                        pos[d1][d2].pop_back();
-                                        --j;
+                        REP(i,(int)pos[d1][d2].size()) {
+                                FOR(j,i+1,(int)pos[d1][d2].size()-1) {
+                                        if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
+                                                pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
+                                                pos[d1][d2].pop_back();
+                                                --j;
+                                        }
                                 }
                         }
+                        done[d1][d2] = true;
                 }
 
@@ -244,15 +247,17 @@
                                 }
                         }
-                }
-                REP(i,(int)pos[d1][d2].size()) {
-                        FOR(j,i+1,(int)pos[d1][d2].size()-1) {
-                                if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
-                                        pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
-                                        pos[d1][d2].pop_back();
-                                        --j;
+                        REP(i,(int)pos[d1][d2].size()) {
+                                FOR(j,i+1,(int)pos[d1][d2].size()-1) {
+                                        if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
+                                                pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
+                                                pos[d1][d2].pop_back();
+                                                --j;
+                                        }
                                 }
                         }
+                        done[d1][d2] = true;
                 }
                 d1 = charnum(c1); d2 = charnum(c2);
+                if(d1>d2) swap(d1,d2);
 
                 ok=false;