QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164418#7180. Forward-Capturing PawnsPhantomThreshold#WA 178ms171456kbC++204.4kb2023-09-04 22:54:322023-09-04 22:54:32

Judging History

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

  • [2023-09-04 22:54:32]
  • 评测
  • 测评结果:WA
  • 用时:178ms
  • 内存:171456kb
  • [2023-09-04 22:54:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int dx[]={-1,-1,-1,0,0,0,1,1,1};
const int dy[]={-1,0,1,-1,0,1,-1,0,1};

struct osc{
	int bw,pr;
	int bi,bj;
	int wi,wj;
	int pi,pj;
	int getid(){
		/*bw,pr,bi,bj,wi,wj,pi,pj*/
		/*01,01,03,03,03,03,03,03*/
		return (bw<<19)|(pr<<18)|(bi<<15)|(bj<<12)|(wi<<9)|(wj<<6)|(pi<<3)|(pj);
	}
	bool check(){
		if (pr==0){
			if (bi==pi && (bj==pj+1)) return true;
			if (pj==1 && bi==pi && (bj==pj+2)) return true;
		}
		else{
			if (bi==pi || bj==pj) return true;
		}
		return false;
	}
	bool takepawn(){
		return (bw==0 && abs(bi-pi)<=1 && abs(bj-pj)<=1 && (abs(wi-pi)>1 || abs(wj-pj)>1));
	}
	bool ok(){
		if (bi<0 || bi>7) return false;
		if (bj<0 || bj>7) return false;
		if (wi<0 || wi>7) return false;
		if (wj<0 || wj>7) return false;
		if (pi<0 || pi>7) return false;
		if (pj<0 || pj>7) return false;
		if (abs(bi-wi)<=1 && abs(bj-wj)<=1) return false;
		if (bi==pi && bj==pj) return false;
		if (wi==pi && wj==pj) return false;
		if (bw==1 && check()) return false;
		return true;
	}
	bool checkmate(){
		if (bw==1) return false;
		if (!check()) return false;
		if (takepawn()) return false;
		osc nxt=(*this);
		nxt.bw^=1;
		for (int k=0;k<9;k++){
			nxt.bi=bi+dx[k];
			nxt.bj=bj+dy[k];
			if (nxt.ok()) return false;
		}
		return true;
	}
};

const int maxn=1<<22;
int dp[maxn+50];
vector<int> g[maxn+50];
int deg[maxn+50];
int act[maxn+50];

inline void addedge(int u,int v){
	g[u].emplace_back(v);
	deg[v]++;	
}
inline int getbw(int x){
	return (x>>19)&1;	
}

void prepare(){
	
	queue<int> q;
	
	for (int bw=0;bw<=1;bw++){
		for (int pr=0;pr<=1;pr++){
			for (int bi=0;bi<=7;bi++){
				for (int bj=0;bj<=7;bj++){
					for (int wi=0;wi<=7;wi++){
						for (int wj=0;wj<=7;wj++){
							for (int pi=0;pi<=7;pi++){
								for (int pj=0;pj<=7;pj++){
									osc now=(osc){bw,pr,bi,bj,wi,wj,pi,pj};
									if (!now.ok()) continue;
									int nowid=now.getid();
									
									if (now.takepawn()) deg[nowid]++;
									if (now.checkmate()){
										dp[nowid]=1;
									//	cerr << "nowid : " << nowid << endl;
									//	cerr << "list : " << endl;
									//	cerr << bw << " " << pr << " ";
										q.push(nowid);	
									}
									
									if (bw==0){
										for (int k=0;k<9;k++){
											osc nxt=now;
											nxt.bw^=1;
											nxt.bi+=dx[k];
											nxt.bj+=dy[k];
											if (!nxt.ok()) continue;
											addedge(nxt.getid(),nowid);
										}
									}
									else{
										for (int k=0;k<9;k++){
											osc nxt=now;
											nxt.bw^=1;
											nxt.wi+=dx[k];
											nxt.wj+=dy[k];
											if (!nxt.ok()) continue;
											addedge(nxt.getid(),nowid);
										}
										if (pr==0){
											int ed=(now.pj==1)?(2):(1);
											for (int k=1;k<=ed;k++){
												osc nxt=now;
												nxt.bw^=1;
												nxt.pj+=k;
												if (!nxt.ok()) continue;
												addedge(nxt.getid(),nowid);
											}
										}
										else{
											for (int k=1;k<=8;k++){
												if (k==pi) continue;
												osc nxt=now;
												nxt.bw^=1;
												nxt.pi=k;
												if (!nxt.ok()) continue;
												addedge(nxt.getid(),nowid);
											}
											for (int k=1;k<=8;k++){
												if (k==pj) continue;
												osc nxt=now;
												nxt.bw^=1;
												nxt.pj=k;
												if (!nxt.ok()) continue;
												addedge(nxt.getid(),nowid);
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	
	for (;!q.empty();){
		int u=q.front();
		q.pop();
		for (auto v:g[u]) if (!dp[v]){
			++act[v];
			if (getbw(v)==1){
				dp[v]=1;
				q.push(v);
			}
			else{
				if (act[v]==deg[v]){
					dp[v]=1;
					q.push(v);
				}
			}
		}
	}
	
}

int main(){
	prepare();
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	for (;T--;){
		string strw,strp,strb,strbw;
		cin >> strw >> strp >> strb >> strbw;
		int bw=0,pr=0;
		int bi=0,bj=0;
		int wi=0,wj=0;
		int pi=0,pj=0;
		bw=(strbw[0]=='w');
		
		bi=(strb[0]-'a');
		bj=(strb[1]-'1');
		
		wi=(strw[0]-'a');
		wj=(strw[1]-'1');
		
		pi=(strp[0]-'a');
		pj=(strp[1]-'1');
		osc now=(osc){bw,pr,bi,bj,wi,wj,pi,pj};
		int id=now.getid();
		if (dp[id]==1) cout << "Win" << "\n";
		else cout << "Draw" << "\n";
	}
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 178ms
memory: 171456kb

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:

Draw
Draw
Draw
Draw
Draw
Draw

result:

wrong answer 3rd lines differ - expected: 'Win', found: 'Draw'