[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]F False Intelligence

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
const int And[3][3]={{0,0,0},{0,1,1},{0,1,2}};
const int Or[3][3]={{0,1,2},{1,1,2},{2,2,2}};
const int Implies[3][3]={{2,2,2},{1,2,2},{0,1,2}};
const int Equals[3][3]={{2,0,0},{0,2,0},{0,0,2}};

char readchar() {char ch;while ((ch=getchar())!='F' && ch!='U' && ch!='T');return ch;}

struct Matrix
{
	int a[3][3];

	int Hash()
	{
		int res=0;
		for (int i=0,xx=1;i<9;i++) res+=a[i/3][i%3]*xx,xx*=3;
		return res;
	}

	int *operator[] (int x) {return a[x];}
}M[maxn];

Matrix AND(Matrix &a,Matrix &b)
{
	Matrix res;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		res[i][j]=And[a[i][j]][b[i][j]];
	return res;
}


Matrix OR(Matrix &a,Matrix &b)
{
	Matrix res;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		res[i][j]=Or[a[i][j]][b[i][j]];
	return res;
}

Matrix IMPLIES(Matrix &a,Matrix &b)
{
	Matrix res;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		res[i][j]=Implies[a[i][j]][b[i][j]];
	return res;
}

Matrix EQUALS(Matrix &a,Matrix &b)
{
	Matrix res;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		res[i][j]=Equals[a[i][j]][b[i][j]];
	return res;
}

Matrix temp;
int q[maxn];
int vis[maxn];

void Init()
{
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		temp[i][j]=And[i][j];
	q[0]=temp.Hash();
	M[q[0]]=temp;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		temp[i][j]=Or[i][j];
	q[1]=temp.Hash();
	M[q[1]]=temp;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		temp[i][j]=Implies[i][j];
	q[2]=temp.Hash();
	M[q[2]]=temp;
	for (int i=0;i<3;i++)
	for (int j=0;j<3;j++)
		temp[i][j]=Equals[i][j];
	q[3]=temp.Hash();
	M[q[3]]=temp;
	vis[q[0]]=vis[q[1]]=vis[q[2]]=vis[q[3]]=1;
	int qtop=0,qtail=3;
	while (qtop<=qtail)
	{
		for (int i=0;i<qtop;i++)
		{
			Matrix M1;
			int h;
			M1=AND(M[q[qtop]],M[q[i]]);
			h=M1.Hash();
			if (!vis[h]) vis[h]=1,q[++qtail]=h,M[h]=M1;
			M1=OR(M[q[qtop]],M[q[i]]);
			h=M1.Hash();
			if (!vis[h]) vis[h]=1,q[++qtail]=h,M[h]=M1;
			M1=IMPLIES(M[q[qtop]],M[q[i]]);
			h=M1.Hash();
			if (!vis[h]) vis[h]=1,q[++qtail]=h,M[h]=M1;
			M1=EQUALS(M[q[qtop]],M[q[i]]);
			h=M1.Hash();
			if (!vis[h]) vis[h]=1,q[++qtail]=h,M[h]=M1;
		}
		qtop++;
	}
}

int n;

int main()
{
	freopen("test.in","r",stdin);
	Init();
	scanf("%d",&n);
	while (n--)
	{
		char ch;
		for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
			if ((ch=readchar())=='F') temp[i][j]=0;
		else
			if (ch=='U') temp[i][j]=1;
		else
			if (ch=='T') temp[i][j]=2;
		if (vis[temp.Hash()]) printf("definable\n");else printf("undefinable\n");
	}
}