QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166187#7180. Forward-Capturing Pawnsucup-team987#TL 0ms0kbC++207.5kb2023-09-06 01:43:362023-09-06 01:43:37

Judging History

你现在查看的是最新测评结果

  • [2023-09-06 01:43:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-09-06 01:43:36]
  • 提交

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&&deg[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");
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: