QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732018#9537. Chinese Chessvme50WA 37ms4076kbC++172.9kb2024-11-10 12:45:032024-11-10 12:45:05

Judging History

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

  • [2024-11-10 12:45:05]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:4076kb
  • [2024-11-10 12:45:03]
  • 提交

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.