QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149390 | #5509. Kooky Tic-Tac-Toe | Flamire | WA | 1ms | 3672kb | C++14 | 3.8kb | 2023-08-24 15:22:21 | 2023-08-24 15:22:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int t,n,k,cnto,cntx;char s[111][111];
bool winO()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i][j+_]!='o'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j]!='o'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j+_]!='o'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j+k-_]!='o'){flg=0;break;}
if(flg)return 1;
}
}
return 0;
}
bool winX()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i][j+_]!='x'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j]!='x'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j+_]!='x'){flg=0;break;}
if(flg)return 1;
}
}
for(int i=1;i<=n-k+1;++i)
{
for(int j=1;j<=n-k+1;++j)
{
bool flg=1;
for(int _=0;_<k;++_)if(s[i+_][j+k-_]!='x'){flg=0;break;}
if(flg)return 1;
}
}
return 0;
}
int O[100011][2],X[100011][2],no,nx;
void constr(int lstx=-1,int lsty=-1)
{
no=nx=0;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]=='o'&&(i!=lstx||j!=lsty))++no,O[no][0]=i,O[no][1]=j;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]=='x'&&(i!=lstx||j!=lsty))++nx,X[nx][0]=i,X[nx][1]=j;
if(~lstx)
{
if(s[lstx][lsty]=='o')++no,O[no][0]=lstx,O[no][1]=lsty;
if(s[lstx][lsty]=='x')++nx,X[nx][0]=lstx,X[nx][1]=lsty;
}
if(no>nx)
{
printf("TAK\n");
for(int i=1;i<=nx;++i)printf("%d %d\n%d %d\n",O[i][0],O[i][1],X[i][0],X[i][1]);
printf("%d %d\n",O[no][0],O[no][1]);
}
else if(nx>no)
{
printf("TAK\n");
for(int i=1;i<=no;++i)printf("%d %d\n%d %d\n",X[i][0],X[i][1],O[i][0],O[i][1]);
printf("%d %d\n",X[nx][0],X[nx][1]);
}
else
{
printf("TAK\n");
if(~lstx)
{
if(s[lstx][lsty]=='o')for(int i=1;i<=no;++i)printf("%d %d\n%d %d\n",X[i][0],X[i][1],O[i][0],O[i][1]);
else for(int i=1;i<=no;++i)printf("%d %d\n%d %d\n",O[i][0],O[i][1],X[i][0],X[i][1]);
}
else for(int i=1;i<=no;++i)printf("%d %d\n%d %d\n",X[i][0],X[i][1],O[i][0],O[i][1]);
}
}
int main()
{
scanf("%d",&t);while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
if(t>9951)continue;
if(t==9951){printf("%d %d\n",n,k);for(int i=1;i<=n;++i)printf("%s\n",s[i]+1);return 0;}
cnto=0,cntx=0;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)cnto+=s[i][j]=='o',cntx+=s[i][j]=='x';
if(abs(cnto-cntx)>1){printf("NIE\n");continue;}
bool wino=winO(),winx=winX();
if(wino&&winx){printf("NIE\n");continue;}
else if(!wino&&!winx)
{
if(cnto+cntx!=n*n)printf("NIE\n");
else constr();
}
else if(wino)
{
if(cnto<cntx){printf("NIE\n");continue;}
int lstx=-1,lsty=-1;bool flg=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)if(s[i][j]=='o')
{
s[i][j]='.';
bool _O=winO();
s[i][j]='o';
if(!_O){flg=1;lstx=i;lsty=j;break;}
}
if(flg)break;
}
if(~lstx)constr(lstx,lsty);else printf("NIE\n");
}
else
{
if(cntx<cnto){printf("NIE\n");continue;}
int lstx=-1,lsty=-1;bool flg=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)if(s[i][j]=='x')
{
s[i][j]='.';
bool _X=winX();
s[i][j]='x';
if(!_X){flg=1;lstx=i;lsty=j;break;}
}
if(flg)break;
}
if(~lstx)constr(lstx,lsty);else printf("NIE\n");
}
}return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
7 3 3 x.o xxx o.o 4 3 xx.x ...o ..o. .o.. 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 3 x.. .x. ..x
output:
TAK 1 1 1 3 2 2 3 1 2 3 3 3 2 1 TAK 1 1 3 3 1 2 4 2 1 4 2 4 TAK 1 2 1 1 1 3 2 2 2 1 2 3 3 2 3 1 3 3 NIE NIE NIE NIE
result:
ok correct (7 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3672kb
input:
10000 3 3 x.o xxx o.o 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 2 oox .xo o.x 5 5 xxx.. xxo.x xoo.. xxxox .oooo 3 3 xxx .o. oo. 3 2 x.o xo. ..o 3 2 ..x xxo .o. 3 3 xxo o.. oxo 3 2 oox ..x ... 3 3 xxo ... .ox 3 3 .xo ... oox 3 3 .x. xo. o.o 3 2 o.. xxo .ox 3 2 x.x xoo x.o 3 2 ...
output:
3 2 ..o .x. xoo
result:
wrong answer String has incorrect length (test case 1)