#include #include #include #include #include #include #include #include using namespace std; #define int long long #define endl "\n" constexpr long long INF = (long long)1e18; constexpr long long MOD = 1'000'000'007; struct fast_io { fast_io(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); }; } fio; bool solve(string &S){ int N = S.size(); for(int i = 0; i < N - 2; i++){ string x; x += S[i]; x += S[i+1]; x += S[i+2]; if(x == "ooo") return true; if(x == "oo-") return true; if(x == "o-o") return true; if(x == "-oo") return true; if(i+3>=N)continue; x += S[i+3]; if(x == "-o--") return true; if(x == "--o-") return true; } return false; } map field; int check(string &S){ int N = S.size(); int cono= 0, conx = 0; for(int i = 0; i < N; i++){ if(S[i] == 'x') conx++; else cono++; } if(cono < conx) return -1; if(cono - 1> conx) return -1; for(int i = 0; i < N - 2; i++){ if(S[i] == 'o' && S[i+1] == 'o' && S[i+2] == 'o') return true; } return false; } int test(string &S, int t){ int temp = field[S]; if(temp != -1) return temp; bool flag = false; int con = 0; for(int i = 0; i < S.size(); i++){ if(S[i] != '-') continue; con++; if(t) { S[i] = 'o'; if(test(S, !t) == t) flag = true; } else { S[i] = 'x'; if(test(S, !t) == t) flag = true; } S[i] = '-'; } if(con == 0){ field[S] = check(S); } else { if(flag) field[S] = t; else field[S] = !t; } return field[S]; } void test2(int num){ field.clear(); string S; int x = 1; for(int i = 0; i < num; i++){ x *= 3; S += '-'; } for(int i = 0; i < x; i++){ string z; int con = 0, d = i; for(int j = 0; j < num; j++, d /= 3){ if(d%3 == 0) z += '-', con++; else if(d%3 == 1) z += 'o'; else if(d%3 == 2) z += 'x'; } field[z] = -1; // if(con) field[z] = -1; // else field[z] = check(z); } test(S, 1); int con = 0; for(int i = 0; i < x; i++){ string z; int d = i; for(int j = 0; j < num; j++, d /= 3){ if(d%3 == 0) z += '-'; else if(d%3 == 1) z += 'o'; else if(d%3 == 2) z += 'x'; } // if(cono < conx) return -1; // if(cono - 1> conx) return -1; if(field[z] == 1) con++; if(field[z] == 1)cout<