QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #166187 | #7180. Forward-Capturing Pawns | ucup-team987# | TL | 0ms | 0kb | C++20 | 7.5kb | 2023-09-06 01:43:36 | 2023-09-06 01:43:37 |
answer
#include<iostream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<cassert>
#define NDEBUG
using namespace std;
vector<int>RG[8*8*8*8*8*8*2*6];
int deg[8*8*8*8*8*8*2*6];
int tp[8*8*8*8*8*8*2*6];
int VTX(int wkx,int wky,int wpx,int wpy,int bkx,int bky,int turn,int promo)
{
return ((((((wkx*8+wky)*8+wpx)*8+wpy)*8+bkx)*8+bky)*2+turn)*6+promo;
}
const int dx[8]={0,1,0,-1,1,1,-1,-1};
const int dy[8]={1,0,-1,0,1,-1,1,-1};
void dfs(int wkx,int wky,int wpx,int wpy,int bkx,int bky,int turn,int promo)
{
if(promo!=5)
{
assert(!(wkx==wpx&&wky==wpy));
assert(!(wpx==bkx&&wpy==bky));
}
assert(!(wkx==bkx&&wky==bky));
if(promo==0)assert(wpy<7);
assert(0<=wkx&&wkx<8);
assert(0<=wky&&wky<8);
assert(0<=wpx&&wpx<8);
assert(0<=wpy&&wpy<8);
assert(0<=bkx&&bkx<8);
assert(0<=bky&&bky<8);
assert(0<=turn&&turn<2);
assert(0<=promo&&promo<6);
assert(abs(wkx-bkx)>=2||abs(wky-bky)>=2);
int U=VTX(wkx,wky,wpx,wpy,bkx,bky,turn,promo);
if(tp[U])return;
tp[U]=-1;//now searching
if(turn==0)
{//white turn
{//king move
for(int r=0;r<8;r++)
{
int nx=wkx+dx[r],ny=wky+dy[r];
if(nx<0||ny<0||8<=nx||8<=ny)continue;//outside
if(nx==wpx&&ny==wpy)continue;//coinside
if(nx==bkx&&ny==bky)
{//catch bk
assert(false);
}
if(abs(nx-bkx)<=1&&abs(ny-bky)<=1)continue;//cought by bk
int V=VTX(nx,ny,wpx,wpy,bkx,bky,1-turn,promo);
deg[U]++;
RG[V].push_back(U);
dfs(nx,ny,wpx,wpy,bkx,bky,1-turn,promo);
}
}
if(promo==0)
{//pawn move
for(int dy=1;dy<=(wpy==1?2:1);dy++)
{
int nx=wpx,ny=wpy+dy;
assert(ny<8);
if(nx==wkx&&ny==wky)break;//coinside; not go to dy==2
if(nx==bkx&&ny==bky)
{//catch bk
assert(false);
}
if(ny<7)
{
int V=VTX(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
}
else
{
for(int p=1;p<5;p++)
{
int V=VTX(wkx,wky,nx,ny,bkx,bky,1-turn,p);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nx,ny,bkx,bky,1-turn,p);
}
}
}
}
if(promo==1||promo==3)
{//queen, bishop; diagonal
for(int r=4;r<8;r++)
{
int nx=wpx,ny=wpy;
while(true)
{
nx+=dx[r],ny+=dy[r];
if(nx<0||ny<0||8<=nx||8<=ny)break;//outside
if(nx==wkx&&ny==wky)break;//coinside
if(nx==bkx&&ny==bky)
{//catch bk
assert(false);
}
int V=VTX(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
}
}
}
if(promo==1||promo==2)
{//queen, rook; diagonal
for(int r=0;r<4;r++)
{
int nx=wpx,ny=wpy;
while(true)
{
nx+=dx[r],ny+=dy[r];
if(nx<0||ny<0||8<=nx||8<=ny)break;//outside
if(nx==wkx&&ny==wky)break;//coinside
if(nx==bkx&&ny==bky)
{//catch bk
assert(false);
}
int V=VTX(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
}
}
}
if(promo==4)
{//knight
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={2,1,-1,-2,-2,-1,1,2};
for(int r=0;r<8;r++)
{
int nx=wpx+dx[r],ny=wpy+dy[r];
if(nx<0||ny<0||8<=nx||8<=ny)continue;//outside
if(nx==wkx&&ny==wky)continue;//coinside
if(nx==bkx&&ny==bky)
{//catch bk
assert(false);
}
int V=VTX(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nx,ny,bkx,bky,1-turn,promo);
}
}
}
else
{
for(int r=0;r<8;r++)
{
int nx=bkx+dx[r],ny=bky+dy[r];
if(nx<0||ny<0||8<=nx||8<=ny)continue;//outside
if(nx==wkx&&ny==wky)
{//catch wk
assert(false);
}
if(abs(nx-wkx)<=1&&abs(ny-wky)<=1)continue;//cought by wk
int np=promo;
int nwpx=wpx,nwpy=wpy;
if(nx==wpx&&ny==wpy)
{
np=5;
nwpx=nwpy=0;
}
else
{
if(promo==0)
{//white pawn
if(wpx==nx&&wpy+1==ny)continue;
if(wpy==1&&!(wpx==wkx&&wpy+1==wky)&&wpx==nx&&wpy+2==ny)continue;
}
if(promo==1||promo==3)
{//diagonal
int dx=wpx-nx,dy=wpy-ny;
if(abs(dx)==abs(dy))
{
//king between
int kdx=wpx-wkx,kdy=wpy-wky;
if(abs(kdx)==abs(kdy)&&abs(kdx)<abs(dx)&&dx*kdx>0&&dy*kdy>0);
else continue;
}
}
if(promo==1||promo==2)
{//horizontal
int dx=wpx-nx,dy=wpy-ny;
if(dx==0)
{
//king between
int kdy=wpy-wky;
if(wpx==wkx&&abs(kdy)<abs(dy)&&kdy*dy>0);
else continue;
}
else if(dy==0)
{
//king between
int kdx=wpx-wkx;
if(wpy==wky&&abs(kdx)<abs(dx)&&kdx*dx>0);
else continue;
}
}
if(promo==4)
{//knight
int dx=wpx-nx,dy=wpy-ny;
if(abs(dx)==1&&abs(dy)==2||
abs(dx)==2&&abs(dy)==1)continue;
}
}
int V=VTX(wkx,wky,nwpx,nwpy,nx,ny,1-turn,np);
deg[U]++;
RG[V].push_back(U);
dfs(wkx,wky,nwpx,nwpy,nx,ny,1-turn,np);
}
}
if(deg[U]);
else
{
if(turn==0)
{//white; not attacked
//cout<<wkx<<" "<<wky<<" "<<wpx<<" "<<wpy<<" "<<bkx<<" "<<bky<<" "<<turn<<" "<<promo<<endl;
tp[U]=2;
//assert(false);
}
else
{
bool at=false;
int nx=bkx,ny=bky;
if(promo==0)
{//white pawn
if(wpx==nx&&wpy+1==ny)at=true;
if(wpy==1&&!(wpx==wkx&&wpy+1==wky)&&wpx==nx&&wpy+2==ny)at=true;
}
if(promo==1||promo==3)
{//diagonal
int dx=wpx-nx,dy=wpy-ny;
if(abs(dx)==abs(dy))
{
//king between
int kdx=wpx-wkx,kdy=wpy-wky;
if(abs(kdx)==abs(kdy)&&abs(kdx)<abs(dx)&&dx*kdx>0&&dy*kdy>0);
else at=true;
}
}
if(promo==1||promo==2)
{//horizontal
int dx=wpx-nx,dy=wpy-ny;
if(dx==0)
{
//king between
int kdy=wpy-wky;
if(wpx==wkx&&abs(kdy)<abs(dy)&&kdy*dy>0);
else at=true;
}
else if(dy==0)
{
//king between
int kdx=wpx-wkx;
if(wpy==wky&&abs(kdx)<abs(dx)&&kdx*dx>0);
else at=true;
}
}
if(promo==4)
{//night
int dx=wpx-nx,dy=wpy-ny;
if(abs(dx)==1&&abs(dy)==2||
abs(dx)==2&&abs(dy)==1)at=true;
}
if(at)tp[U]=1;
else tp[U]=2;//stalemate
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
vector<int>Q(T);
vector<char>C(T);
auto rd=[]()->pair<int,int>{
string s;cin>>s;
assert(s.size()==2);
int x=(int)s[0]-'a';
assert(0<=x&&x<8);
int y=(int)s[1]-'1';
assert(0<=y&&y<8);
return make_pair(x,y);
};
for(int i=0;i<T;i++)
{
auto wk=rd();
auto wp=rd();
auto bk=rd();
char c;cin>>c;
int U=VTX(wk.first,wk.second,
wp.first,wp.second,
bk.first,bk.second,
(c=='w'?0:1),
0);
Q[i]=U;
dfs(wk.first,wk.second,
wp.first,wp.second,
bk.first,bk.second,
(c=='w'?0:1),
0);
C[i]=c;
}
const int N=8*8*8*8*8*8*2*6;
vector<int>que;
for(int u=0;u<N;u++)if(tp[u]!=0&°[u]==0)
{
assert(tp[u]!=-1);
que.push_back(u);
}
for(int i=0;i<que.size();i++)
{
int u=que[i];
for(int v:RG[u])
{
deg[v]--;
if(tp[u]==1)
{
if(tp[v]!=3)
{
tp[v]=3;
que.push_back(v);
}
}
else if(deg[v]==0&&tp[v]!=3)
{
tp[v]=1;
que.push_back(v);
}
}
}
for(int i=0;i<T;i++)
{
int ans=tp[Q[i]];
if(ans==-1)ans=2;
ans-=2;
char c=C[i];
if(c=='w')
{
assert(ans==0||ans==1);
cout<<(ans==0?"Draw\n":"Win\n");
}
else
{
assert(ans==0||ans==-1);
cout<<(ans==0?"Draw\n":"Win\n");
}
}
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
6 a2 d7 e7 w b6 d7 e7 b b6 d7 e7 w b5 a2 b2 w a6 a2 a4 b g6 g7 h8 b