QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732076 | #9537. Chinese Chess | vme50 | TL | 203ms | 5400kb | C++17 | 3.2kb | 2024-11-10 13:03:19 | 2024-11-10 13:03:20 |
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> mask[6],z[N][N][N];
vector<int> vc[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);
}
}
bool chk(bitset<M> stt)
{
int cnt=0;
for(int i=0;i<6;++i)
{
if((stt&mask[i]).any()) ++cnt;
if(cnt>1) return 0;
}
return 1;
}
int slv(bitset<M> stt)
{
if(chk(stt)) 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(auto k:vc[i][j])
{
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) break;
}
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);
for(int i=0;i<M;++i) mask[i%6].set(i);
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);
}
}
for(int i=0;i<=9;++i)
for(int j=0;j<=8;++j)
for(int k=0;k<=20;++k)
if(z[i][j][k].any())
vc[i][j].eb(k);
bitset<M> stt;
stt.set();
printf("%d\n",slv(stt));
fflush(stdout);
while(1)
{
if(chk(stt))
{
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: 0ms
memory: 3980kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 2ms
memory: 4020kb
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: 0
Accepted
time: 1ms
memory: 4032kb
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: 4044kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 0ms
memory: 4284kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
2 7 7 1 0 -1 6
output:
2 ? 0 0 ? 7 2 ! S
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 4ms
memory: 4096kb
input:
5 8 6 1 3 0 5 2 4 0 2 6 3
output:
2 ? 0 0 ? 0 3 ! J
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 13ms
memory: 4136kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 -1 14
output:
2 ? 0 0 ? 8 1 ! B
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 13ms
memory: 4136kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 5 7
output:
2 ? 0 0 ? 0 4 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 24ms
memory: 4204kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 7 -1
output:
2 ? 0 1 ? 0 0 ! S
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 203ms
memory: 5400kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 6 8
output:
2 ? 2 0 ? 0 0 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 2ms
memory: 4060kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 186ms
memory: 5400kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #14:
score: 0
Accepted
time: 4ms
memory: 4052kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #15:
score: 0
Accepted
time: 11ms
memory: 4392kb
input:
9 4 6 4 5 4 7 4 4 4 1 4 3 4 0 4 8 4 2 6 12
output:
2 ? 4 2 ? 0 0 ! J
result:
ok number is guessed.
Test #16:
score: 0
Accepted
time: 4ms
memory: 4320kb
input:
10 9 2 5 2 1 2 8 2 6 2 7 2 2 2 0 2 4 2 3 2 10 3
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #17:
score: 0
Accepted
time: 149ms
memory: 5132kb
input:
9 3 1 3 7 3 5 3 3 3 6 3 4 3 0 3 2 3 8 6 11
output:
2 ? 3 2 ? 0 0 ! J
result:
ok number is guessed.
Test #18:
score: 0
Accepted
time: 4ms
memory: 4076kb
input:
10 5 1 8 1 6 1 4 1 3 1 0 1 2 1 7 1 9 1 1 1 10 -1
output:
2 ? 9 0 ? 0 0 ! B
result:
ok number is guessed.
Test #19:
score: 0
Accepted
time: 191ms
memory: 5316kb
input:
9 1 6 1 4 1 3 1 7 1 8 1 5 1 2 1 1 1 0 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #20:
score: 0
Accepted
time: 4ms
memory: 4096kb
input:
10 5 0 9 0 1 0 2 0 3 0 6 0 7 0 4 0 0 0 8 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #21:
score: 0
Accepted
time: 199ms
memory: 5344kb
input:
9 0 3 0 5 0 7 0 0 0 4 0 8 0 1 0 6 0 2 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #22:
score: 0
Accepted
time: 4ms
memory: 4128kb
input:
10 1 0 9 0 4 0 2 0 8 0 7 0 5 0 3 0 0 0 6 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #23:
score: 0
Accepted
time: 191ms
memory: 5316kb
input:
9 1 8 1 2 1 7 1 0 1 4 1 6 1 1 1 5 1 3 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #24:
score: 0
Accepted
time: 4ms
memory: 4356kb
input:
10 2 4 1 4 0 4 6 4 4 4 9 4 5 4 3 4 7 4 8 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #25:
score: 0
Accepted
time: 203ms
memory: 5344kb
input:
9 0 2 0 7 0 5 0 4 0 0 0 3 0 1 0 6 0 8 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #26:
score: 0
Accepted
time: 4ms
memory: 4008kb
input:
10 5 3 2 3 3 3 8 3 9 3 1 3 6 3 7 3 0 3 4 3 11 4
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #27:
score: -100
Time Limit Exceeded
input:
50 7 5 9 2 0 4 9 3 8 4 8 2 7 2 6 4 4 4 0 0 1 7 1 1 1 5 2 0 9 8 9 0 3 1 7 8 8 6 5 0 7 3 8 5 2 6 4 8 3 5 6 8 0 8 5 7 4 6 1 6 3 8 5 6 3 0 5 3 0 7 5 1 3 4 0 1 7 6 2 3 4 3 5 5 8 1 0 3 6 5 9 5 5 8 7 4 6 3 2 7