fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/iwDKdu
language:
C++ (gcc 8.3)
created:
57 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!