Участник:ArtemTovkes/ADAQUBIC

Материал из DISCOPAL
Перейти к: навигация, поиск

C++ (gcc 8.3) https://www.spoj.com/problems/ADAQUBIC/

#include <bits/stdc++.h>
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
 
int main(){
	int tc;
	cin >> tc;
	map <string, int> dp;
	const vi dr = {1, 0, 0, 1, 1, 0, 1};
	const vi dc = {0, 1, 0, 1, 0, 1, 1};
	const vi dk = {0, 0, 1, 0, 1, 1, 1};
	const vi order = {13,
					   4, 10, 12, 14, 16, 22,
					   1, 3, 5, 7, 19, 21, 23, 25,
					   0, 2, 6, 8, 9, 11, 15, 17, 18, 20, 24, 26};
	while(tc--){
		string grid = "";
		for (int i=0; i<9; i++){
			string s;
			cin >> s;
			grid += s;
		}
		const int LOSE = 0;
		const int WIN = 1;
		auto is_winner = [&] (const string& s) -> bool {
			for (int i = 0; i < sz(s); i += 3){
				if (s[i] != '.' and s[i] == s[i+1] and s[i] == s[i+2]) return true;
			}
			for (int k = 0; k<3; k++){
				for (int c = 0; c<3; c++){
					int p = 9*k + c;
					if (s[p] != '.' and s[p] == s[p+3] and s[p] == s[p+6]) return true;
				}
				int p = 9*k;
				if (s[p] != '.' and s[p] == s[p+4] and s[p] == s[p+8]) return true;
				p += 2;
				if (s[p] != '.' and s[p] == s[p+2] and s[p] == s[p+4]) return true;
			}
			for (int r = 0; r <3; r++) {
				for (int c = 0; c<3; c++){
					int p =3*r +c;
					if (s[p] != '.' and s[p] == s[p+9] and s[p] == s[p+18]) return true;
				}
			}
			for (int c = 0; c<3; c++){
				int p = c;
				if (s[p] != '.' and s[p] == s[p+12] and s[p] == s[p+24]) return true;
				p += 6;
				if (s[p] != '.' and s[p] == s[p+6] and s[p] == s[p+12]) return true;
			}
			for (int r = 0; r<3; r++){
				int p = 3*r;
				if (s[p] != '.' and s[p] == s[p+10] and s[p] == s[p+20]) return true;
				p += 2;
				if (s[p] != '.' and s[p] == s[p+8] and s[p] == s[p+16]) return true;
			}
			if (s[0] != '.' and s[0] == s[13] and s[0] == s[26]) return true;
			if (s[2] != '.' and s[2] == s[13] and s[2] == s[24]) return true;
			if (s[6] != '.' and s[6] == s[13] and s[6] == s[20]) return true;
			if (s[8] != '.' and s[8] == s[13] and s[8] == s[18]) return true;
			return false;
		};
		function <int(string, int)> rec = [&] (string s, int turn) -> int {
			if (is_winner(s)) return LOSE;
			if (dp.count(s)) return dp[s];
			char nxt = (turn) ? 'x' : 'o';
			char other = (turn) ? 'o' : 'x';
			int ret = LOSE;
			vi direct_lose;
			for (int i = 0; i < sz(s); i++) {
				if (s[i] != '.') continue;
				s[i] = nxt;
				if (is_winner(s)) return dp[s] = WIN;
				s[i] = other;
				if (is_winner(s)) direct_lose.pb(i);
				s[i] = '.';
			}
			if (sz(direct_lose) >= 2) return dp[s] = LOSE;
			if (sz(direct_lose) == 1) {
				s[direct_lose[0]] = nxt;
				if (rec(s, turn ^ 1) == LOSE) ret = WIN;
				s[direct_lose[0]] = '.';
				return dp[s] = ret;
			}
			for (int c: order) {
				if (ret == WIN) break;
				if (s[c] != '.') continue;
				s[c] = nxt;
				if (rec(s, turn ^ 1) == LOSE) ret = WIN;
				s[c] = '.';
			}
			return dp[s] = ret;
		};
		int x = count(all(grid), 'x');
		int y = count(all(grid), 'o');
		if (rec(grid, (x==y)) == LOSE) {
			if (x==y) cout << "Vinit\n";
			else cout << "Ada\n";
		} else {
			if (x==y) cout << "Ada\n";
			else cout << "Vinit\n";
		}
	}
	return (0);
}