Source code for submission s1006

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 res1[25][25];
  123. int res2[25][25];
  124.  
  125. int table(char c) {
  126. switch(c) {
  127. case 'F': return 0;
  128. case 'I': return 1;
  129. case 'L': return 2;
  130. case 'N': return 3;
  131. case 'P': return 4;
  132. case 'T': return 5;
  133. case 'U': return 6;
  134. case 'V': return 7;
  135. case 'W': return 8;
  136. case 'X': return 9;
  137. case 'Y': return 10;
  138. case 'Z': return 11;
  139. }
  140. }
  141.  
  142. struct Bod{
  143. int x, y;
  144. bool operator<(const Bod &p) const {
  145. return (x<p.x || (x==p.x && y<p.y));
  146. }
  147. bool operator==(const Bod &p) const {
  148. return (x==p.x && y==p.y);
  149. }
  150. };
  151. struct Konfig{
  152. Bod body[10];
  153. bool operator<(const Konfig &p) const {
  154. for(int i=0;i<10;++i){
  155. if(body[i]<p.body[i])
  156. return true;
  157.  
  158. if(p.body[i]<body[i])
  159. return false;
  160. }
  161.  
  162. return false;
  163. }
  164. bool operator==(const Konfig &p) const {
  165. for(int i=0;i<10;++i){
  166. if(!(body[i]==p.body[i]))
  167. return false;
  168. }
  169. return true;
  170. }
  171. void sortp(){
  172. sort(body, body+10);
  173. }
  174. };
  175.  
  176. vector<Konfig> dobre[12][12];
  177.  
  178. void generate(int p1, int p2){
  179. //bool exist = 0;
  180. vector<Konfig> nonuni;
  181.  
  182. REP(i, 8) REP(j, 8) REP(x1, 6) REP(y1, 6) {
  183. REP(p, 20) REP(q, 20) res1[p][q] = 0;
  184. REP(p, 5) REP(q, 5) {
  185. char c = poz[p1][i][p][q];
  186. res1[p][q] += (c=='X')?1:0;
  187. c = poz[p2][j][p][q];
  188. res1[p+x1][q+y1] += (c=='X')?1:0;
  189. }
  190. bool kolize = 0;
  191. REP(p, 12) REP(q, 12) if (res1[p][q]>1) kolize = 1;
  192. if (kolize) continue;
  193.  
  194. int pp1, qq1;
  195. REP(p, 12) REP(q, 12) {
  196. if (res1[p][q]==1) {
  197. pp1 = p; qq1 = q; goto pryc1;
  198. }
  199. }
  200. pryc1:
  201.  
  202. Konfig k;
  203. int bi = 0;
  204. REP(p, 12) REP(q, 12){
  205. if(res1[p][q]){
  206. k.body[bi].x = p-pp1;
  207. k.body[bi].y = q-qq1;
  208. ++bi;
  209. }
  210. }
  211.  
  212. nonuni.push_back(k);
  213.  
  214. }
  215.  
  216. REP(i, nonuni.size())
  217. nonuni[i].sortp();
  218.  
  219. sort(nonuni.begin(),nonuni.end());
  220.  
  221. int ui = 0;
  222. REP(i, nonuni.size()){
  223. if(i == 0 || !(nonuni[i]==nonuni[i-1])){
  224. dobre[min(p1,p2)][max(p2,p1)].push_back(nonuni[i]);
  225. }
  226. }
  227.  
  228. // printf("%d\n",dobre[p1][p2].size());
  229. }
  230.  
  231.  
  232. void solve() {
  233. REP(i, 4) a[i] = table(A[i]);
  234.  
  235. if(a[0]>a[1])
  236. swap(a[0], a[1]);
  237. if(a[2]>a[3])
  238. swap(a[2], a[3]);
  239.  
  240. //int poz2 = 0;
  241. bool ok = 0;
  242. REP(i, dobre[a[0]][a[1]].size())
  243. REP(j, dobre[a[2]][a[3]].size())
  244. if( dobre[a[0]][a[1]][i]== dobre[a[2]][a[3]][j]){
  245. ok = 1;
  246. goto ven;
  247. }
  248.  
  249. //for(int poz1=0;poz1<dobre[a[0]][a[1]].size();++poz1);
  250.  
  251. ven:
  252. printf("%s\n", ok?"YES":"NO");
  253. }
  254.  
  255. int main() {
  256. REP(i, 12) {
  257. //REP(k, 4) {
  258. REP(x, 5) REP(y, 5) {
  259. poz[i][0][x][y] = P[i][x][y];
  260. poz[i][1][x][y] = P[i][4-x][y];
  261. poz[i][2][x][y] = P[i][x][4-y];
  262. poz[i][3][x][y] = P[i][4-x][4-y];
  263. poz[i][4][x][y] = P[i][y][x];
  264. poz[i][5][x][y] = P[i][4-y][4-x];
  265. poz[i][6][x][y] = P[i][y][4-x];
  266. poz[i][7][x][y] = P[i][4-y][x];
  267. }
  268. //}
  269. }
  270.  
  271. REP(i, 12) FOR(j, i, 11)
  272. { generate(i, j); generate(j,i); }
  273. while (scanf(" %c %c %c %c", &A[0], &A[1], &A[2], &A[3]) != EOF) {
  274. solve();
  275. }
  276. /*REP(i, 12) FOR(j, i, 11) REP(k, 12) FOR (l, k, 11) {
  277. a[0] = i; a[1] = j; a[2] = k; a[3] = l;
  278. solve();
  279. }*/
  280. return 0;
  281. }
  282.  
  283. /*
  284.  
  285. REP(i, 12) REP(j, 8) sort(ppp[i][j].begin(), ppp[i][j].end());
  286.  
  287. REP(i, 12) REP(j, 8) REP(k, 5) REP(l, 5) {
  288. if (poz[i][j][k][l]=='X')
  289. ppp[i][j].push_back((Pozice){k,l});
  290. }
  291.  
  292. bool sloz(int a, i, int b, int j, vector<Pozice> &poz) {
  293. vector<Pozice> ans;
  294. REP(q, ppp[a][i].size()) ans.push_back(ppp[a][i][q]);
  295. REP(q, ppp[b][j].size()) ans.push_back(ppp[b][j][q]);
  296. sort(ans.begin(), ans.end());
  297. REP(i, ans.size()-1) if (ans[i]==ans[i+1]) return false;
  298. return true;
  299. }
  300.  
  301.  
  302.  
  303. REP(k, 8) REP(l, 8) REP(x2, 5) REP(y2, 5) {
  304. REP(p, 10) REP(q, 10) res2[p][q] = 0;
  305. REP(p, 5) REP(q, 5) {
  306. char c = poz[a[2]][k][p][q];
  307. res2[p][q] += (c=='X')?1:0;
  308. c = poz[a[3]][l][p][q];
  309. res2[p+x2][q+y2] += (c=='X')?1:0;
  310. }
  311. bool kolize = 0;
  312. REP(p, 10) REP(q, 10) if (res2[p][q]>1) kolize = 1;
  313. if (kolize) continue;
  314.  
  315. bool stejne = 1;
  316. int pp1, qq1, pp2, qq2;
  317. REP(p, 10) REP(q, 10) {
  318. if (res1[p][q]==1) {
  319. pp1 = p; qq1 = q; goto pryc1;
  320. }
  321. }
  322. pryc1:
  323. REP(p, 10) REP(q, 10) {
  324. if (res2[p][q]==1) {
  325. pp2 = p; qq2 = q; goto pryc2;
  326. }
  327. }
  328. pryc2:
  329.  
  330. REP(p, 10) REP(q, 10) if (res1[p+pp1][q+qq1]!=res2[p+pp2][q+qq2]) stejne = false;
  331. if (stejne) {
  332. exist = true;
  333. goto ven;
  334. }
  335. }
  336. */
  337.  

Diff to submission s990

fp.cpp

--- c5.s990.cteam022.fp.cpp.0.fp.cpp
+++ c5.s1006.cteam022.fp.cpp.0.fp.cpp
@@ -120,5 +120,4 @@
 int a[4];
 char poz[12][8][5][6];
-int op[4][2] = {{1,1}, {1, -1}, {-1, 1}, {-1, -1}};
 int res1[25][25];
 int res2[25][25];
@@ -177,7 +176,4 @@
 vector<Konfig> dobre[12][12];
 
-
-//vector<Pozice> ppp[12][8];
-
 void generate(int p1, int p2){
         //bool exist = 0;
@@ -226,5 +222,5 @@
         REP(i, nonuni.size()){
                 if(i == 0 || !(nonuni[i]==nonuni[i-1])){
-                        dobre[p1][p2].push_back(nonuni[i]);
+                        dobre[min(p1,p2)][max(p2,p1)].push_back(nonuni[i]);
                 }
         }
@@ -274,5 +270,5 @@
 
         REP(i, 12) FOR(j, i, 11)
-                generate(i, j);
+                { generate(i, j); generate(j,i); }
         while (scanf(" %c %c %c %c", &A[0], &A[1], &A[2], &A[3]) != EOF) {
                 solve();