QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #166192 | #7180. Forward-Capturing Pawns | ucup-team987# | WA | 1694ms | 425212kb | C++20 | 8.4kb | 2023-09-06 01:47:54 | 2023-09-06 01:47:55 |
Judging History
answer
#include<iostream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<cassert>
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
} // namespace internal
} // namespace atcoder
#define NDEBUG
using namespace std;
vector<pair<int,int> >edge;
//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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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]++;
edge.push_back(make_pair(V,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;
atcoder::internal::csr<int>RG(N,edge);
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 id=RG.start[u];id<RG.start[u+1];id++)
{
int v=RG.elist[id];
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: 100
Accepted
time: 1488ms
memory: 422728kb
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 Win Win Draw Draw
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 1694ms
memory: 425212kb
input:
332912 h8 h7 f8 b h8 h7 f8 w h8 h7 e8 b h8 h7 e8 w h8 h7 d8 b h8 h7 d8 w h8 h7 c8 b h8 h7 c8 w h8 h7 b8 b h8 h7 b8 w h8 h7 a8 b h8 h7 a8 w h8 h7 f7 b h8 h7 f7 w h8 h7 e7 b h8 h7 e7 w h8 h7 d7 b h8 h7 d7 w h8 h7 c7 b h8 h7 c7 w h8 h7 b7 b h8 h7 b7 w h8 h7 a7 b h8 h7 a7 w h8 h7 h6 b h8 h7 h6 w h8 h7 g...
output:
Win Draw Win Win Win Win Win Win Win Win Win Win Win Draw Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Win Wi...
result:
wrong answer 1st lines differ - expected: 'Draw', found: 'Win'