QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731860 | #9537. Chinese Chess | vme50 | RE | 1ms | 4136kb | C++17 | 2.5kb | 2024-11-10 11:59:34 | 2024-11-10 11:59:35 |
Judging History
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)
{
printf("! ");
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};
}
}
assert(dp[(1<<6)-1]<INF);
printf("%d\n",dp[(1<<6)-1]);
fflush(stdout);
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: 100
Accepted
time: 1ms
memory: 3844kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 1ms
memory: 4136kb
input:
4 2 1 2 3 2 5 2 7 5 2
output:
2 ? 0 0 ? 5 4 ! M
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: -100
Runtime Error
input:
2 7 7 1 0