QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164418 | #7180. Forward-Capturing Pawns | PhantomThreshold# | WA | 178ms | 171456kb | C++20 | 4.4kb | 2023-09-04 22:54:32 | 2023-09-04 22:54:32 |
Judging History
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'