QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732033#9537. Chinese Chessvme50TL 473ms4800kbC++173.0kb2024-11-10 12:48:002024-11-10 12:48:01

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 12:48:01]
  • 评测
  • 测评结果:TL
  • 用时:473ms
  • 内存:4800kb
  • [2024-11-10 12:48:00]
  • 提交

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];
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(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);
	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);
		}
	}
	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: 2ms
memory: 4300kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 40ms
memory: 4056kb

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: 2ms
memory: 3940kb

input:

1
2 4
-1
1

output:

2
? 0 0
? 0 2
! X

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 2ms
memory: 4284kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 0ms
memory: 4292kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 8ms
memory: 4020kb

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: 109ms
memory: 4416kb

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: 195ms
memory: 4220kb

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: 375ms
memory: 4760kb

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: 473ms
memory: 4800kb

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: -100
Time Limit Exceeded

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: