QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#715093 | #9537. Chinese Chess | as_lyr | WA | 686ms | 4040kb | C++14 | 2.8kb | 2024-11-06 10:24:15 | 2024-11-06 10:24:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=540,M=10,V=20,B=6,n=9,m=8;
char s[B]={'J','S','C','M','X','B'};
bitset <N> bt[B];
bitset <N> bs[M][M][V];
int dis[N][N];
queue <pair<int,int>> q;
void work(int x,int y,int ds){
if(x<0||x>n||y<0||y>m)
return ;
if(ds<dis[x][y]){
dis[x][y]=ds;
q.push(make_pair(x,y));
}
}
void bfs(int o,int u,int v){
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dis[i][j]=V-1;
dis[u][v]=0;
q.push(make_pair(u,v));
while(q.empty()==0){
int x=q.front().first,y=q.front().second;
q.pop();
switch(o){
case 0:
work(x-1,y,dis[x][y]+1);
work(x+1,y,dis[x][y]+1);
work(x,y-1,dis[x][y]+1);
work(x,y+1,dis[x][y]+1);
break;
case 1:
work(x-1,y-1,dis[x][y]+1);
work(x+1,y-1,dis[x][y]+1);
work(x-1,y+1,dis[x][y]+1);
work(x+1,y+1,dis[x][y]+1);
break;
case 2:
for(int i=0;i<=n;i++)
work(i,y,dis[x][y]+1);
for(int i=0;i<=m;i++)
work(x,i,dis[x][y]+1);
break;
case 3:
work(x-2,y-1,dis[x][y]+1);
work(x+2,y-1,dis[x][y]+1);
work(x-2,y+1,dis[x][y]+1);
work(x+2,y+1,dis[x][y]+1);
work(x-1,y-2,dis[x][y]+1);
work(x+1,y-2,dis[x][y]+1);
work(x-1,y+2,dis[x][y]+1);
work(x+1,y+2,dis[x][y]+1);
break;
case 4:
work(x-2,y-2,dis[x][y]+1);
work(x+2,y-2,dis[x][y]+1);
work(x-2,y+2,dis[x][y]+1);
work(x+2,y+2,dis[x][y]+1);
break;
case 5:
work(x+1,y,dis[x][y]+1);
if(x>4){
work(x,y-1,dis[x][y]+1);
work(x,y+1,dis[x][y]+1);
}
break;
}
}
}
void init(){
for(int o=0;o<B;o++)
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
bt[o][6*((m+1)*i+j)+o]=1;
for(int o=0;o<B;o++)
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++){
bfs(o,i,j);
for(int x=0;x<=n;x++)
for(int y=0;y<=m;y++)
bs[x][y][dis[x][y]][6*((m+1)*i+j)+o]=1;
}
}
int ans;
int dfs(int c,bitset <N> b,bool op){
for(int o=0;o<B;o++)
if((b&bt[o])==b){
if(op){
while(ans--){
printf("? 0 0\n");
fflush(stdout);
int x;
scanf("%d",&x);
}
printf("! %c\n",s[o]);
fflush(stdout);
}
return 0;
}
if(c>3)
return 1;
int mx=5-c,x=0,y=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++){
int res=0;
for(int k=0;k<V;k++)
res=max(res,dfs(c+1,b&bs[i][j][k],0)+1);
if(res<mx)
mx=res,x=i,y=j;
mx=min(mx,res+1);
}
if(op){
if(c==1){
ans=mx;
printf("%d\n",ans);
}
printf("? %d %d\n",x,y);
fflush(stdout);
int k;
scanf("%d",&k);
ans--;
dfs(c+1,b&bs[x][y][k],1);
}
return mx;
}
void solve(){
int T;
scanf("%d",&T);
bitset <N> b;
while(T--){
int x,y;
scanf("%d%d",&x,&y);
for(int o=0;o<B;o++)
b[6*((m+1)*x+y)+o]=1;
}
dfs(1,b,1);
}
int main(){
init();
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 242ms
memory: 3948kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 686ms
memory: 3968kb
input:
4 2 1 2 3 2 5 2 7 5 1
output:
2 ? 0 0 ? 0 6 ! M
result:
ok number is guessed.
Test #3:
score: -100
Wrong Answer
time: 234ms
memory: 4040kb
input:
1 2 4 -1 -1
output:
2 ? 0 0 ? 0 0 ! J
result:
wrong answer guessed type is incorrect.