QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732018 | #9537. Chinese Chess | vme50 | WA | 37ms | 4076kb | C++17 | 2.9kb | 2024-11-10 12:45:03 | 2024-11-10 12:45:05 |
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=25,M=540,INF=1e9;
int n,d[N][N];queue<pii> q;
bitset<M> z[N][N][N];
struct Cmp
{
bool operator () (const bitset<M> &a,const bitset<M> &b) const
{
int t=(a^b)._Find_first();
return t<M && a[t]<b[t];
}
};
map<bitset<M>,tuple<int,int,int>,Cmp> mp;
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 slv(bitset<M> stt)
{
if(stt.count()<2) return 0;
if(mp.count(stt)) return get<0>(mp[stt]);
auto &[w,x,y]=mp[stt];
w=INF;
for(int i=0;i<=9;++i)
for(int j=0;j<=8;++j)
{
int t=0;
for(int k=0;k<=20;++k)
if(z[i][j][k].any())
{
bitset<M> stt1=stt&z[i][j][k];
if(stt1.count()<stt.count())
t=max(t,slv(stt1)+1);
else t=INF;
}
if(t<w) w=t,x=i,y=j;
}
return w;
}
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].set(n*6+type);
}
}
bitset<M> stt;
stt.set();
printf("%d\n",slv(stt));
fflush(stdout);
while(1)
{
if(stt.count()<2)
{
answer(stt._Find_first()%6);
break;
}
auto [w,x,y]=mp[stt];
stt&=z[x][y][qry(x,y)+1];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4076kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 4068kb
input:
4 2 1 2 3 2 5 2 7
output:
3 ? 0 1
result:
wrong answer solution think m=3, while jury think m=2.