QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731857 | #9537. Chinese Chess | vme50 | RE | 0ms | 0kb | C++17 | 2.4kb | 2024-11-10 11:57:46 | 2024-11-10 11:57:47 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>
#define eb emplace_back
#define po pop_back
#define par __builtin_parity
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lg __lg
#define gcd __gcd
#define fi first
#define se second
const int N=15,M=105,INF=1e9;
int n,dp[M],d[N][N],z[N][N][M];pii o[M];
queue<pii> q;
void ext1(int x,int y,int w)
{
if(x>=0 && x<=9 && y>=0 && y<=8 && d[x][y]==-1)
d[x][y]=w,q.push({x,y});
}
void ext(int x,int y,int w,int type)
{
if(type==0)
{
ext1(x+1,y,w);
ext1(x-1,y,w);
ext1(x,y+1,w);
ext1(x,y-1,w);
}
else if(type==1)
{
ext1(x+1,y+1,w);
ext1(x+1,y-1,w);
ext1(x-1,y+1,w);
ext1(x-1,y-1,w);
}
else if(type==2)
{
for(int i=0;i<=8;++i) ext1(x,i,w);
for(int i=0;i<=9;++i) ext1(i,y,w);
}
else if(type==3)
{
ext1(x+2,y+1,w);
ext1(x+2,y-1,w);
ext1(x-2,y+1,w);
ext1(x-2,y-1,w);
ext1(x+1,y+2,w);
ext1(x+1,y-2,w);
ext1(x-1,y+2,w);
ext1(x-1,y-2,w);
}
else if(type==4)
{
ext1(x+2,y+2,w);
ext1(x+2,y-2,w);
ext1(x-2,y+2,w);
ext1(x-2,y-2,w);
}
else
{
if(x<=4) ext1(x+1,y,w);
else
{
ext1(x+1,y,w);
ext1(x,y+1,w);
ext1(x,y-1,w);
}
}
}
void bfs(int sx,int sy,int type)
{
for(int i=0;i<=9;++i)
for(int j=0;j<=8;++j)
d[i][j]=-1;
ext1(sx,sy,0);
while(!q.empty())
{
auto [x,y]=q.front();q.pop();
ext(x,y,d[x][y]+1,type);
}
}
int qry(int x,int y)
{
printf("? %d %d\n",x,y);
fflush(stdout);
int t;
scanf("%d",&t);
return t;
}
void answer(int x)
{
putchar("JSCMXB"[x]);
fflush(stdout);
}
int main()
{
scanf("%d",&n);
while(n--)
{
int x,y;
scanf("%d %d",&x,&y);
for(int type=0;type<6;++type)
{
bfs(x,y,type);
for(int i=0;i<=9;++i)
for(int j=0;j<=8;++j)
z[i][j][d[i][j]+1]|=1<<type;
}
}
for(int stt=0;stt<1<<6;++stt)
{
if(pct(stt)<2) continue;
dp[stt]=INF;
for(int i=0;i<=9;++i)
for(int j=0;j<=8;++j)
{
int t=0;
for(int k=0;k<=100;++k)
t=max(t,dp[stt&z[i][j][k]]+1);
if(t<dp[stt]) dp[stt]=t,o[stt]={i,j};
}
}
for(int stt=(1<<6)-1;;)
{
assert(stt);
if(pct(stt)<2)
{
answer(lg(stt));
break;
}
auto [x,y]=o[stt];
stt&=z[x][y][qry(x,y)+1];
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
1 9 0
output:
? 1 8