fork download
  1. //-----------------CODED BY ROCKHOPPER130-----------------
  2. #include <bits/stdc++.h>
  3. #pragma GCC optimize ("O3")
  4.  
  5. #define MOD 1000000007
  6. // #define int long long
  7. #define nish signed
  8. using namespace std;
  9.  
  10. //#include<ext/pb_ds/assoc_container.hpp>
  11. //#include<ext/pb_ds/tree_policy.hpp>
  12. //using namespace __gnu_pbds;
  13.  
  14. //#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  15.  
  16. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  17.  
  18. int T = 0;
  19.  
  20. //--------------------------DEBUG-------------------------
  21.  
  22. void __print(int32_t x) { cerr << x; }
  23. void __print(long x) { cerr << x; }
  24. void __print(long long x) { cerr << x; }
  25. void __print(unsigned x) { cerr << x; }
  26. void __print(unsigned long x) { cerr << x; }
  27. void __print(unsigned long long x) { cerr << x; }
  28. void __print(float x) { cerr << x; }
  29. void __print(double x) { cerr << x; }
  30. void __print(long double x) { cerr << x; }
  31. void __print(char x) { cerr << '\'' << x << '\''; }
  32. void __print(const char *x) { cerr << '"' << x << '"'; }
  33. void __print(const string &x) { cerr << '"' << x << '"'; }
  34. void __print(bool x) { cerr << (x ? "true" : "false"); }
  35. template <typename A>
  36. void __print(const A &x);
  37. template <typename A, typename B>
  38. void __print(const pair<A, B> &p);
  39. template <typename... A>
  40. void __print(const tuple<A...> &t);
  41. template <typename T>
  42. void __print(stack<T> s);
  43. template <typename T>
  44. void __print(queue<T> q);
  45. template <typename T, typename... U>
  46. void __print(priority_queue<T, U...> q);
  47. template <typename A>
  48. void __print(const A &x) {
  49. bool first = true;
  50. cerr << '{';
  51. for (const auto &i : x) {
  52. cerr << (first ? "" : ","), __print(i);
  53. first = false;
  54. }
  55. cerr << '}';
  56. }
  57. template <typename A, typename B>
  58. void __print(const pair<A, B> &p) {
  59. cerr << '(';
  60. __print(p.first);
  61. cerr << ',';
  62. __print(p.second);
  63. cerr << ')';
  64. }
  65. template <typename... A>
  66. void __print(const tuple<A...> &t) {
  67. bool first = true;
  68. cerr << '(';
  69. apply([&first](const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
  70. cerr << ')';
  71. }
  72. template <typename T>
  73. void __print(stack<T> s) {
  74. vector<T> debugVector;
  75. while (!s.empty()) {
  76. T t = s.top();
  77. debugVector.push_back(t);
  78. s.pop();
  79. }
  80. reverse(debugVector.begin(), debugVector.end());
  81. __print(debugVector);
  82. }
  83. template <typename T>
  84. void __print(queue<T> q) {
  85. vector<T> debugVector;
  86. while (!q.empty()) {
  87. T t = q.front();
  88. debugVector.push_back(t);
  89. q.pop();
  90. }
  91. __print(debugVector);
  92. }
  93. template <typename T, typename... U>
  94. void __print(priority_queue<T, U...> q) {
  95. vector<T> debugVector;
  96. while (!q.empty()) {
  97. T t = q.top();
  98. debugVector.push_back(t);
  99. q.pop();
  100. }
  101. __print(debugVector);
  102. }
  103. void _print() { cerr << "]\n"; }
  104. template <typename Head, typename... Tail>
  105. void _print(const Head &H, const Tail &...T) {
  106. __print(H);
  107. if (sizeof...(T))
  108. cerr << ", ";
  109. _print(T...);
  110. }
  111. #ifndef ONLINE_JUDGE
  112. #define debug(...) cerr << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
  113. #else
  114. #define debug(...)
  115. #endif
  116.  
  117. //-----------------------PRE FUNCTIONS----------------------
  118.  
  119. int gcdExtended(int a, int b, int* x, int* y) {
  120. // Base Case
  121. if (a == 0) {
  122. *x = 0, *y = 1;
  123. return b;
  124. }
  125. // To store results of recursive call
  126. int x1, y1;
  127. int gcd = gcdExtended(b % a, a, &x1, &y1);
  128. // Update x and y using results of recursive call
  129. *x = y1 - (b / a) * x1;
  130. *y = x1;
  131. return gcd;
  132. }
  133.  
  134. int modInverse(int A) {
  135. int x, y;
  136. int g = gcdExtended(A, MOD, &x, &y);
  137. if (g != 1)
  138. cout << "Inverse doesn't exist";
  139. else
  140. return (x % MOD + MOD) % MOD;
  141. }
  142.  
  143. int ncr(int n, int r) {
  144. int sum = 1;
  145. for(int i = 1; i <= r; i++){
  146. sum = (sum * (n - r + i) % MOD) * modInverse(i);
  147. sum %= MOD;
  148. }
  149. return sum;
  150. }
  151.  
  152. int qpow(int x,int y) {
  153. int ans = 1;
  154. while(y) {
  155. if(y & 1) ans = ans * x % MOD;
  156. x = x * x % MOD;
  157. y >>= 1;
  158. }
  159. return ans;
  160. }
  161.  
  162. //----------------------------...----------------------------
  163.  
  164. int winner(vector<string> &curr, char target) {
  165. // checkRow
  166. int flag1 = 0;
  167. for(int i = 0; i < 6; i++) {
  168. for(int j = 0; j < 4; j++) {
  169. int temp = 1;
  170. for(int k = j; k < j + 4; k++) {
  171. if(curr[i][k] != target) temp = 0;
  172. }
  173. if(temp) flag1 = 1;
  174. }
  175. }
  176.  
  177. // checkCol
  178. int flag2 = 0;
  179. for(int i = 0; i < 7; i++) {
  180. for(int j = 0; j < 3; j++) {
  181. int temp = 1;
  182. for(int k = j; k < j + 4; k++) {
  183. if(curr[k][i] != target) temp = 0;
  184. }
  185. if(temp) flag2 = 1;
  186. }
  187. }
  188.  
  189. // checkDiag
  190. int flag3 = 0;
  191. for(int i = 0; i < 6; i++) {
  192. for(int j = 0; j < 7; j++) {
  193. int temp = 1;
  194. for(int k = 0; k < 4; k++) {
  195. int ni = i + k;
  196. int nj = j + k;
  197. if(ni >= 0 && ni < 6 && nj >= 0 && nj < 7)
  198. if(curr[ni][nj] != target) temp = 0;
  199. else temp = 0;
  200. }
  201. if(temp) flag3 = 1;
  202.  
  203. temp = 1;
  204. for(int k = 0; k < 4; k++) {
  205. int ni = i - k;
  206. int nj = j + k;
  207. if(ni >= 0 && ni < 6 && nj >= 0 && nj < 7)
  208. if(curr[ni][nj] != target) temp = 0;
  209. else temp = 0;
  210. }
  211. if(temp) flag3 = 1;
  212.  
  213. temp = 1;
  214. for(int k = 0; k < 4; k++) {
  215. int ni = i + k;
  216. int nj = j - k;
  217. if(ni >= 0 && ni < 6 && nj >= 0 && nj < 7)
  218. if(curr[ni][nj] != target) temp = 0;
  219. else temp = 0;
  220. }
  221. if(temp) flag3 = 1;
  222.  
  223. temp = 1;
  224. for(int k = 0; k < 4; k++) {
  225. int ni = i - k;
  226. int nj = j - k;
  227. if(ni >= 0 && ni < 6 && nj >= 0 && nj < 7)
  228. if(curr[ni][nj] != target) temp = 0;
  229. else temp = 0;
  230. }
  231. if(temp) flag3 = 1;
  232. }
  233. }
  234.  
  235. if(flag1 || flag2 || flag3) return 1;
  236. return 0;
  237. }
  238.  
  239. // curr : 0 -> 'C', 1 -> 'F'
  240. int dfs(int turn, int num, vector<string> &curr, vector<string> &v, vector<int> &h) {
  241. if(num == 43) return 0;
  242.  
  243. int k = winner(curr, 'C') + 2 * winner(curr, 'F'); // 0 : No one, 1 : C, 2 : F
  244. if(k != 0) return k;
  245.  
  246. array<int,2> otpt;
  247. for(int i = 0; i < 7; i++) {
  248. if(h[i] < 6) {
  249. char toFind = ((turn % 2) ? 'F' : 'C');
  250. if(v[h[i]][i] != toFind) continue;
  251.  
  252. curr[h[i]][i] = toFind;
  253. h[i]++;
  254.  
  255. int temp = dfs(turn ^ 1, num + 1, curr, v, h);
  256.  
  257. curr[h[i]][i] = '.';
  258. h[i]--;
  259.  
  260. if(temp == 1) otpt[0] = 1;
  261. else if(temp == 2) otpt[1] = 1;
  262. else if(temp == 3) otpt[0] = 1, otpt[1] = 1;
  263. }
  264. }
  265.  
  266. return otpt[0] + 2 * otpt[1];
  267. }
  268.  
  269. void solve(){
  270. T++;
  271.  
  272. vector<string> v(6);
  273. for(int i = 0; i < 6; i++) cin >> v[i];
  274.  
  275. vector<string> curr(6, string(7,'.'));
  276. vector<int> h(7, 0);
  277.  
  278. int otpt = dfs(0, 1, curr, v, h);
  279.  
  280. if(otpt == 3) cout << "?\n";
  281. else if(otpt == 2) cout << "F\n";
  282. else if(otpt == 1) cout << "C\n";
  283. else if(otpt == 0) cout << "0\n";
  284. }
  285.  
  286. nish main() {
  287.  
  288. ios::sync_with_stdio(0);
  289. cin.tie(0);
  290.  
  291. int test = 1;
  292. cin >> test;
  293. int test_tot = test;
  294.  
  295. while(test--){
  296. cout << "Case #" << test_tot - test << ": ";
  297. solve();
  298. }
  299.  
  300. return 0;
  301. }
Runtime error #stdin #stdout 0.04s 5272KB
stdin
4

FFFFFFF
CCCCCCC
FFFFFFF
CCCCCCC
FFFFFFF
CCCCCCC

FCFCFCF
FCCFCFC
CFFCFCF
CFCFCFC
CFCFFCF
CFCFCFC

FCFCFCF
CCFCFCF
CFCFCCF
CFFFCFC
FCCCCCC
CFFFFFF

FCFCFCF
CFCFCFC
FCFCFCF
FCFCFCF
CFCFCFC
CFCFCFC
stdout
Standard output is empty