QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #847916 | #4234. Tic Tac Toe Counting | HeyJinhwi# | WA | 2ms | 4516kb | C++14 | 6.8kb | 2025-01-08 13:15:53 | 2025-01-08 13:15:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int arr[3][3];
vector<int> adj[20000];
int pw[3][3];
int is_valid(int k)
{
int t=k;
int cnt_x=0,cnt_o=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(t%3==1)cnt_x++;
if(t%3==2)cnt_o++;
arr[i][j]=t%3;
t/=3;
}
}
if(cnt_x!=cnt_o&&cnt_x!=cnt_o+1)return 0;
int row_x=0,row_o=0;
for(int i=0;i<3;i++)
{
row_x++;
for(int j=0;j<3;j++)
{
if(arr[i][j]!=1)
{
row_x--;
break;
}
}
row_x++;
for(int j=0;j<3;j++)
{
if(arr[j][i]!=1)
{
row_x--;
break;
}
}
}
row_x++;
for(int i=0;i<3;i++)
{
if(arr[i][i]!=1)
{
row_x--;
break;
}
}
row_x++;
for(int i=0;i<3;i++)
{
if(arr[i][2-i]!=1)
{
row_x--;
break;
}
}
for(int i=0;i<3;i++)
{
row_o++;
for(int j=0;j<3;j++)
{
if(arr[i][j]!=2)
{
row_o--;
break;
}
}
row_o++;
for(int j=0;j<3;j++)
{
if(arr[j][i]!=2)
{
row_o--;
break;
}
}
}
row_o++;
for(int i=0;i<3;i++)
{
if(arr[i][i]!=2)
{
row_o--;
break;
}
}
row_o++;
for(int i=0;i<3;i++)
{
if(arr[i][2-i]!=2)
{
row_o--;
break;
}
}
if(row_x&&row_o)return 0;
if(row_x&&cnt_x==cnt_o)return 0;
if(row_o&&cnt_x!=cnt_o)return 0;
if(row_x)return 3;
if(row_o)return 4;
if(cnt_x==cnt_o)return 2;
return 1;
}
typedef pair<int,int> pi;
int a[50000];
int vis[50000];
int cnt_x[20000],cnt_o[20000];
vector<int> dep[10];
main()
{
pw[0][0]=1;
for(int i=1;i<3;i++)
{
pw[i][0]=pw[i-1][0]*27;
}
for(int i=0;i<3;i++)for(int j=1;j<3;j++)pw[i][j]=pw[i][j-1]*3;
for(int i=0;i<19683;i++)
{
int t=is_valid(i);
a[i]=t;
int cnt=0;
int tt=i;
while(tt)
{
if(tt%3)cnt++;
tt/=3;
}
if(t>2)dep[cnt].push_back(i);
}
queue<int> q,qq;
for(int i=9;i;i--)
{
for(int j=0;j<dep[i].size();j++)
{
if(a[dep[i][j]]==3)
{
vis[dep[i][j]]=1;
cnt_x[dep[i][j]]=1;
q.push(dep[i][j]);
}
}
while(!q.empty())
{
int v=q.front();
q.pop();
int u=cnt_x[v];
int tt=v;
for(int k=0;k<3;k++)
{
for(int j=0;j<3;j++)
{
arr[k][j]=tt%3;
tt/=3;
}
}
if(a[v]%2)
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
if(arr[j][k]==1&&a[v-pw[j][k]]==2)
{
cnt_x[v-pw[j][k]]+=u;
if(vis[v-pw[j][k]]==0)
{
qq.push(v-pw[j][k]);
vis[v-pw[j][k]]=1;
}
}
}
}
}
else
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
if(arr[j][k]==2&&a[v-2*pw[j][k]]==1)
{
cnt_x[v-2*pw[j][k]]+=u;
if(vis[v-2*pw[j][k]]==0)
{
qq.push(v-2*pw[j][k]);
vis[v-2*pw[j][k]]=1;
}
}
}
}
}
}
while(!qq.empty())
{
q.push(qq.front());
qq.pop();
}
}
for(int i=0;i<19863;i++)vis[i]=0;
for(int i=9;i;i--)
{
for(int j=0;j<dep[i].size();j++)
{
if(a[dep[i][j]]==4)
{
vis[dep[i][j]]=1;
cnt_o[dep[i][j]]=1;
q.push(dep[i][j]);
}
}
while(!q.empty())
{
int v=q.front();
q.pop();
int u=cnt_o[v];
int tt=v;
for(int k=0;k<3;k++)
{
for(int j=0;j<3;j++)
{
arr[k][j]=tt%3;
tt/=3;
}
}
if(a[v]%2)
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
if(arr[j][k]==1&&a[v-pw[j][k]]==2)
{
cnt_o[v-pw[j][k]]+=u;
if(vis[v-pw[j][k]]==0)
{
qq.push(v-pw[j][k]);
vis[v-pw[j][k]]=1;
}
}
}
}
}
else
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
if(arr[j][k]==2&&a[v-2*pw[j][k]]==1)
{
cnt_o[v-2*pw[j][k]]+=u;
if(vis[v-2*pw[j][k]]==0)
{
qq.push(v-2*pw[j][k]);
vis[v-2*pw[j][k]]=1;
}
}
}
}
}
}
while(!qq.empty())
{
q.push(qq.front());
qq.pop();
}
}
int tc;
scanf("%d",&tc);
char x[11]={};
while(tc--)
{
scanf("%s",x);
int t=0;
for(int i=0;i<9;i++)
{
t*=3;
if(x[i]=='X')t++;
if(x[i]=='O')t+=2;
}
cout<<t<<' '<<a[t]<<' ';
if(a[t]==0)
{
cout<<"-1 -1\n";
}
cout<<cnt_x[t]<<' '<<cnt_o[t]<<'\n';
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 4516kb
input:
4 XX..O.... X...OX... OOOX.X.X. OOOXXX...
output:
8910 1 191 194 6750 1 232 200 19227 4 0 1 19305 0 -1 -1 0 0
result:
wrong answer 1st lines differ - expected: '191 194', found: '8910 1 191 194'