QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#732076#9537. Chinese Chessvme50TL 203ms5400kbC++173.2kb2024-11-10 13:03:192024-11-10 13:03:20

Judging History

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

  • [2024-11-10 13:03:20]
  • 评测
  • 测评结果:TL
  • 用时:203ms
  • 内存:5400kb
  • [2024-11-10 13:03:19]
  • 提交

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;
}

詳細信息

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

output:


result: