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
comments (?)
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
https://ideone.com/iwDKdu
language:
C++ (gcc 8.3)
created:
25 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!