Source code for submission s975

Go to diff to previous submission

fp.cpp

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4.  
  5. #include<cmath>
  6. #include<cctype>
  7. #include<climits>
  8. #include<algorithm>
  9. #include<utility>
  10. #include<string>
  11.  
  12. #include<deque>
  13. #include<list>
  14. #include<map>
  15. #include<queue>
  16. #include<set>
  17. #include<stack>
  18. #include<vector>
  19.  
  20. using namespace std;
  21.  
  22. #define REP(i,N) for (int i = 0; i < (N); i++)
  23. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  24. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  25. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  26. #define DP(arg...) fprintf(stderr, ## arg)
  27.  
  28. typedef long long ll;
  29. typedef long double ld;
  30. typedef pair<int,int> ii;
  31.  
  32. char P[15][5][6] = {
  33. 	{
  34. 		{".XX.."},
  35. 		{"XX..."},
  36. 		{".X..."},
  37. 		{"....."},
  38. 		{"....."}
  39. 	},
  40. 	{
  41. 		{"X...."},
  42. 		{"X...."},
  43. 		{"X...."},
  44. 		{"X...."},
  45. 		{"X...."}
  46. 	},
  47. 	{
  48. 		{"X...."},
  49. 		{"X...."},
  50. 		{"X...."},
  51. 		{"XX..."},
  52. 		{"....."}
  53. 	},
  54. 	{
  55. 		{".X..."},
  56. 		{".X..."},
  57. 		{"XX..."},
  58. 		{"X...."},
  59. 		{"....."}
  60. 	},
  61. 	{
  62. 		{"XX..."},
  63. 		{"XX..."},
  64. 		{"X...."},
  65. 		{"....."},
  66. 		{"....."}
  67. 	},
  68. 	{
  69. 		{"XXX.."},
  70. 		{".X..."},
  71. 		{".X..."},
  72. 		{"....."},
  73. 		{"....."}
  74. 	},
  75. 	{
  76. 		{"X.X.."},
  77. 		{"XXX.."},
  78. 		{"....."},
  79. 		{"....."},
  80. 		{"....."}
  81. 	},
  82. 	{
  83. 		{"X...."},
  84. 		{"X...."},
  85. 		{"XXX.."},
  86. 		{"....."},
  87. 		{"....."}
  88. 	},
  89. 	{
  90. 		{"X...."},
  91. 		{"XX..."},
  92. 		{".XX.."},
  93. 		{"....."},
  94. 		{"....."}
  95. 	},
  96. 	{
  97. 		{".X..."},
  98. 		{"XXX.."},
  99. 		{".X..."},
  100. 		{"....."},
  101. 		{"....."}
  102. 	},
  103. 	{
  104. 		{".X..."},
  105. 		{"XX..."},
  106. 		{".X..."},
  107. 		{".X..."},
  108. 		{"....."}
  109. 	},
  110. 	{
  111. 		{"XX..."},
  112. 		{".X..."},
  113. 		{".XX.."},
  114. 		{"....."},
  115. 		{"....."}
  116. 	}
  117. };
  118.  
  119. char A[4];
  120. int a[4];
  121. char poz[12][8][5][6];
  122. int op[4][2] = {{1,1}, {1, -1}, {-1, 1}, {-1, -1}};
  123. int res1[25][25];
  124. int res2[25][25];
  125.  
  126. int table(char c) {
  127. 	switch(c) {
  128. 		case 'F': return 0;
  129. 		case 'I': return 1;
  130. 		case 'L': return 2;
  131. 		case 'N': return 3;
  132. 		case 'P': return 4;
  133. 		case 'T': return 5;
  134. 		case 'U': return 6;
  135. 		case 'V': return 7;
  136. 		case 'W': return 8;
  137. 		case 'X': return 9;
  138. 		case 'Y': return 10;
  139. 		case 'Z': return 11;
  140. 	}
  141. }
  142.  
  143. struct Bod{
  144. 	int x, y;
  145. 	bool operator<(const Bod &p) const {
  146. 		return (x<p.x || (x==p.x && y<p.y));
  147. 	}
  148. 	bool operator==(const Bod &p) const {
  149. 		return (x==p.x && y==p.y);
  150. 	}
  151. };
  152. struct Konfig{
  153. 	Bod body[10];
  154. 	bool operator<(const Konfig &p) const {
  155. 		for(int i=0;i<10;++i){
  156. 			if(body[i]<p.body[i])
  157. 				return true;
  158.  
  159. 			if(p.body[i]<body[i])
  160. 				return false;
  161. 		}
  162.  
  163. 		return false;
  164. 	}
  165. 	bool operator==(const Konfig &p) const {
  166. 		for(int i=0;i<10;++i){
  167. 			if(!(body[i]==p.body[i]))
  168. 				return false;
  169. 		}
  170. 		return true;
  171. 	}
  172. 	void sortp(){
  173. 		sort(body, body+10);
  174. 	}
  175. };
  176.  
  177. vector<Konfig> dobre[12][12];
  178.  
  179.  
  180. //vector<Pozice> ppp[12][8];
  181.  
  182. void generate(int p1, int p2){
  183. 	//bool exist = 0;
  184. 	vector<Konfig> nonuni;
  185.  
  186. 	REP(i, 8) REP(j, 8) REP(x1, 6) REP(y1, 6) {
  187. 		REP(p, 20) REP(q, 20) res1[p][q] = 0;
  188. 		REP(p, 5) REP(q, 5) {
  189. 			char c = poz[p1][i][p][q];
  190. 			res1[p][q] += (c=='X')?1:0;
  191. 			c = poz[p2][j][p][q];
  192. 			res1[p+x1][q+y1] += (c=='X')?1:0;
  193. 		}
  194. 		bool kolize = 0;
  195. 		REP(p, 10) REP(q, 10) if (res1[p][q]>1) kolize = 1;
  196. 		if (kolize) continue;
  197.  
  198. 		int pp1, qq1;
  199. 		REP(p, 10) REP(q, 10) {
  200. 			if (res1[p][q]==1) {
  201. 				pp1 = p; qq1 = q; goto pryc1;
  202. 			}
  203. 		}
  204. 		pryc1:
  205.  
  206. 		Konfig k;
  207. 		int bi = 0;
  208. 		REP(p, 10) REP(q, 10){
  209. 			if(res1[p][q]){
  210. 				k.body[bi].x = p-pp1;
  211. 				k.body[bi].y = q-qq1;
  212. 				++bi;
  213. 			}
  214. 		}
  215.  
  216. 		nonuni.push_back(k);
  217.  
  218. 	}
  219.  
  220. 	REP(i, nonuni.size())
  221. 		nonuni[i].sortp();
  222.  
  223. 	sort(nonuni.begin(),nonuni.end());
  224.  
  225. 	int ui = 0;
  226. 	REP(i, nonuni.size()){
  227. 		if(i == 0 || !(nonuni[i]==nonuni[i-1])){
  228. 			dobre[p1][p2].push_back(nonuni[i]);
  229. 		}
  230. 	}
  231.  
  232. //	printf("%d\n",dobre[p1][p2].size());
  233. }
  234.  
  235.  
  236. void solve() {
  237. 	REP(i, 4) a[i] = table(A[i]);
  238.  
  239. 	if(a[0]>a[1])
  240. 		swap(a[0], a[1]);
  241. 	if(a[2]>a[3])
  242. 		swap(a[2], a[3]);
  243.  
  244. 	//int poz2 = 0;
  245. 	bool ok = 0;
  246. 	REP(i, dobre[a[0]][a[1]].size())
  247. 		REP(j, dobre[a[2]][a[3]].size())
  248. 			if( dobre[a[0]][a[1]][i]== dobre[a[2]][a[3]][j]){
  249. 				ok = 1;
  250. 				goto ven;
  251. 			}
  252.  
  253. 	//for(int poz1=0;poz1<dobre[a[0]][a[1]].size();++poz1);
  254.  
  255. ven:
  256. 	printf("%s\n", ok?"YES":"NO");
  257. }
  258.  
  259. int main() {
  260. 	REP(i, 12) {
  261. 		//REP(k, 4) {
  262. 			REP(x, 5) REP(y, 5) {
  263. 				poz[i][0][x][y] = P[i][x][y];
  264. 				poz[i][1][x][y] = P[i][4-x][y];
  265. 				poz[i][2][x][y] = P[i][x][4-y];
  266. 				poz[i][3][x][y] = P[i][4-x][4-y];
  267. 				poz[i][4][x][y] = P[i][y][x];
  268. 				poz[i][5][x][y] = P[i][4-y][4-x];
  269. 				poz[i][6][x][y] = P[i][y][4-x];
  270. 				poz[i][7][x][y] = P[i][4-y][x];
  271. 			}
  272. 		//}
  273. 	}
  274.  
  275. 	REP(i, 12) FOR(j, i, 11)
  276. 		generate(i, j);
  277. 	while (scanf(" %c %c %c %c", &A[0], &A[1], &A[2], &A[3]) != EOF) {
  278. 		solve();
  279. 	}
  280. 	/*REP(i, 12) FOR(j, i, 11) REP(k, 12) FOR (l, k, 11) {
  281. 		a[0] = i; a[1] = j; a[2] = k; a[3] = l;
  282. 		solve();
  283. 	}*/
  284. 	return 0;
  285. }
  286.  
  287. /*
  288.  
  289. 	REP(i, 12) REP(j, 8) sort(ppp[i][j].begin(), ppp[i][j].end());
  290.  
  291. 	REP(i, 12) REP(j, 8) REP(k, 5) REP(l, 5) {
  292. 		if (poz[i][j][k][l]=='X')
  293. 			ppp[i][j].push_back((Pozice){k,l});
  294. 	}
  295.  
  296. bool sloz(int a, i, int b, int j, vector<Pozice> &poz) {
  297. 	vector<Pozice> ans;
  298. 	REP(q, ppp[a][i].size()) ans.push_back(ppp[a][i][q]);
  299. 	REP(q, ppp[b][j].size()) ans.push_back(ppp[b][j][q]);
  300. 	sort(ans.begin(), ans.end());
  301. 	REP(i, ans.size()-1) if (ans[i]==ans[i+1]) return false;
  302. 	return true;
  303. }
  304.  
  305.  
  306.  
  307. REP(k, 8) REP(l, 8) REP(x2, 5) REP(y2, 5) {
  308. 			REP(p, 10) REP(q, 10) res2[p][q] = 0;
  309. 			REP(p, 5) REP(q, 5) {
  310. 				char c = poz[a[2]][k][p][q];
  311. 				res2[p][q] += (c=='X')?1:0;
  312. 				c = poz[a[3]][l][p][q];
  313. 				res2[p+x2][q+y2] += (c=='X')?1:0;
  314. 			}
  315. 			bool kolize = 0;
  316. 			REP(p, 10) REP(q, 10) if (res2[p][q]>1) kolize = 1;
  317. 			if (kolize) continue;
  318.  
  319. 			bool stejne = 1;
  320. 			int pp1, qq1, pp2, qq2;
  321. 			REP(p, 10) REP(q, 10) {
  322. 				if (res1[p][q]==1) {
  323. 					pp1 = p; qq1 = q; goto pryc1;
  324. 				}
  325. 			}
  326. 			pryc1:
  327. 			REP(p, 10) REP(q, 10) {
  328. 				if (res2[p][q]==1) {
  329. 					pp2 = p; qq2 = q; goto pryc2;
  330. 				}
  331. 			}
  332. 			pryc2:
  333.  
  334. 			REP(p, 10) REP(q, 10) if (res1[p+pp1][q+qq1]!=res2[p+pp2][q+qq2]) stejne = false;
  335. 			if (stejne) {
  336. 				exist = true;
  337. 				goto ven;
  338. 			}
  339. 		}
  340. */
  341.  

Diff to submission s862

fp.cpp

--- c5.s862.cteam022.fp.cpp.0.fp.cpp
+++ c5.s975.cteam022.fp.cpp.0.fp.cpp
@@ -141,13 +141,53 @@
 }
 
-void solve() {
-        REP(i, 4) a[i] = table(A[i]);
-        bool exist = 0;
-        REP(i, 8) REP(j, 8) REP(x1, 5) REP(y1, 5) {
-                REP(p, 10) REP(q, 10) res1[p][q] = 0;
+struct Bod{
+        int x, y;
+        bool operator<(const Bod &p) const {
+                return (x<p.x || (x==p.x && y<p.y));
+        }
+        bool operator==(const Bod &p) const {
+                return (x==p.x && y==p.y);
+        }
+};
+struct Konfig{
+        Bod body[10];
+        bool operator<(const Konfig &p) const {
+                for(int i=0;i<10;++i){
+                        if(body[i]<p.body[i])
+                                return true;
+                        
+                        if(p.body[i]<body[i])
+                                return false;
+                }
+                
+                return false;
+        }
+        bool operator==(const Konfig &p) const {
+                for(int i=0;i<10;++i){
+                        if(!(body[i]==p.body[i]))
+                                return false;
+                }
+                return true;
+        }
+        void sortp(){
+                sort(body, body+10);
+        }
+};
+
+vector<Konfig> dobre[12][12];
+
+
+//vector<Pozice> ppp[12][8];
+
+void generate(int p1, int p2){
+        //bool exist = 0;
+        vector<Konfig> nonuni;
+        
+        REP(i, 8) REP(j, 8) REP(x1, 6) REP(y1, 6) {
+                REP(p, 20) REP(q, 20) res1[p][q] = 0;
                 REP(p, 5) REP(q, 5) {
-                        char c = poz[a[0]][i][p][q];
+                        char c = poz[p1][i][p][q];
                         res1[p][q] += (c=='X')?1:0;
-                        c = poz[a[1]][j][p][q];
+                        c = poz[p2][j][p][q];
                         res1[p+x1][q+y1] += (c=='X')?1:0;
                 }
@@ -155,5 +195,115 @@
                 REP(p, 10) REP(q, 10) if (res1[p][q]>1) kolize = 1;
                 if (kolize) continue;
-                REP(k, 8) REP(l, 8) REP(x2, 5) REP(y2, 5) {
+                
+                int pp1, qq1;
+                REP(p, 10) REP(q, 10) {
+                        if (res1[p][q]==1) {
+                                pp1 = p; qq1 = q; goto pryc1;
+                        }
+                }
+                pryc1:
+                
+                Konfig k;
+                int bi = 0;
+                REP(p, 10) REP(q, 10){
+                        if(res1[p][q]){
+                                k.body[bi].x = p-pp1;
+                                k.body[bi].y = q-qq1;
+                                ++bi;
+                        }
+                }
+                
+                nonuni.push_back(k);
+                
+        }
+        
+        REP(i, nonuni.size())
+                nonuni[i].sortp();
+                
+        sort(nonuni.begin(),nonuni.end());
+        
+        int ui = 0;
+        REP(i, nonuni.size()){
+                if(i == 0 || !(nonuni[i]==nonuni[i-1])){
+                        dobre[p1][p2].push_back(nonuni[i]);
+                }
+        }
+        
+//      printf("%d\n",dobre[p1][p2].size());
+}
+
+
+void solve() {
+        REP(i, 4) a[i] = table(A[i]);
+        
+        if(a[0]>a[1])
+                swap(a[0], a[1]);
+        if(a[2]>a[3])
+                swap(a[2], a[3]);
+        
+        //int poz2 = 0;
+        bool ok = 0;
+        REP(i, dobre[a[0]][a[1]].size())
+                REP(j, dobre[a[2]][a[3]].size())
+                        if( dobre[a[0]][a[1]][i]== dobre[a[2]][a[3]][j]){
+                                ok = 1;
+                                goto ven;
+                        }
+        
+        //for(int poz1=0;poz1<dobre[a[0]][a[1]].size();++poz1);
+
+ven:
+        printf("%s\n", ok?"YES":"NO");
+}
+
+int main() {
+        REP(i, 12) {
+                //REP(k, 4) {
+                        REP(x, 5) REP(y, 5) {
+                                poz[i][0][x][y] = P[i][x][y];
+                                poz[i][1][x][y] = P[i][4-x][y];
+                                poz[i][2][x][y] = P[i][x][4-y];
+                                poz[i][3][x][y] = P[i][4-x][4-y];
+                                poz[i][4][x][y] = P[i][y][x];
+                                poz[i][5][x][y] = P[i][4-y][4-x];
+                                poz[i][6][x][y] = P[i][y][4-x];
+                                poz[i][7][x][y] = P[i][4-y][x];
+                        }
+                //}
+        }
+
+        REP(i, 12) FOR(j, i, 11)
+                generate(i, j);
+        while (scanf(" %c %c %c %c", &A[0], &A[1], &A[2], &A[3]) != EOF) {
+                solve();
+        }
+        /*REP(i, 12) FOR(j, i, 11) REP(k, 12) FOR (l, k, 11) {
+                a[0] = i; a[1] = j; a[2] = k; a[3] = l;
+                solve();
+        }*/
+        return 0;
+}
+
+/*
+
+        REP(i, 12) REP(j, 8) sort(ppp[i][j].begin(), ppp[i][j].end());
+
+        REP(i, 12) REP(j, 8) REP(k, 5) REP(l, 5) {
+                if (poz[i][j][k][l]=='X')
+                        ppp[i][j].push_back((Pozice){k,l});
+        }
+
+bool sloz(int a, i, int b, int j, vector<Pozice> &poz) {
+        vector<Pozice> ans;
+        REP(q, ppp[a][i].size()) ans.push_back(ppp[a][i][q]);
+        REP(q, ppp[b][j].size()) ans.push_back(ppp[b][j][q]);
+        sort(ans.begin(), ans.end());
+        REP(i, ans.size()-1) if (ans[i]==ans[i+1]) return false;
+        return true;
+}
+
+
+
+REP(k, 8) REP(l, 8) REP(x2, 5) REP(y2, 5) {
                         REP(p, 10) REP(q, 10) res2[p][q] = 0;
                         REP(p, 5) REP(q, 5) {
@@ -188,28 +338,3 @@
                         }
                 }
-        }
-ven:
-        if (exist) printf("YES\n");
-        else printf("NO\n");
-}
-
-int main() {
-        REP(i, 12) {
-                //REP(k, 4) {
-                        REP(x, 5) REP(y, 5) {
-                                poz[i][0][x][y] = P[i][x][y];
-                                poz[i][1][x][y] = P[i][4-x][y];
-                                poz[i][2][x][y] = P[i][x][4-y];
-                                poz[i][3][x][y] = P[i][4-x][4-y];
-                                poz[i][4][x][y] = P[i][y][x];
-                                poz[i][5][x][y] = P[i][4-y][4-x];
-                                poz[i][6][x][y] = P[i][y][4-x];
-                                poz[i][7][x][y] = P[i][4-y][x];
-                        }
-                //}
-        }
-        while (scanf(" %c %c %c %c", &A[0], &A[1], &A[2], &A[3]) != EOF) {
-                solve();
-        }
-        return 0;
-}
+*/