QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #166205 | #7180. Forward-Capturing Pawns | ucup-team987# | AC ✓ | 1256ms | 424064kb | C++20 | 8.5kb | 2023-09-06 01:58:34 | 2023-09-06 01:58:35 |
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(tp[u]==2)
{
if(tp[v]!=3)tp[v]=2;
}
if(deg[v]==0&&tp[v]!=3)
{
if(tp[v]==-1)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");
}
}
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1090ms
memory: 422116kb
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: 0
Accepted
time: 1256ms
memory: 424064kb
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:
Draw Draw Draw Win Win Win Win Win Win Win Win Win Draw Draw Draw Win Win Win Win Win Win Win Win Win Win Win Draw Win Draw 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...
result:
ok 332912 lines
Extra Test:
score: 0
Extra Test Passed