QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731859#9537. Chinese Chessvme50WA 1ms4052kbC++172.5kb2024-11-10 11:59:112024-11-10 11:59:12

Judging History

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

  • [2024-11-10 11:59:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4052kb
  • [2024-11-10 11:59:11]
  • 提交

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=15,M=105,INF=1e9;
int n,dp[M],d[N][N],z[N][N][M];pii o[M];
queue<pii> q;
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 qry(int x,int y)
{
	printf("? %d %d\n",x,y);
	fflush(stdout);
	int t;
	scanf("%d",&t);
	return t;
}
void answer(int x)
{
	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]|=1<<type;
		}
	}
	for(int stt=0;stt<1<<6;++stt)
	{
		if(pct(stt)<2) continue;
		dp[stt]=INF;
		for(int i=0;i<=9;++i)
			for(int j=0;j<=8;++j)
			{
				int t=0;
				for(int k=0;k<=100;++k)
					t=max(t,dp[stt&z[i][j][k]]+1);
				if(t<dp[stt]) dp[stt]=t,o[stt]={i,j};
			}
	}
	assert(dp[(1<<6)-1]<INF);
	printf("%d\n",dp[(1<<6)-1]);
	fflush(stdout);
	for(int stt=(1<<6)-1;;)
	{
		assert(stt);
		if(pct(stt)<2)
		{
			answer(lg(stt));
			break;
		}
		auto [x,y]=o[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: 0
Wrong Answer
time: 1ms
memory: 4052kb

input:

1
9 0
8

output:

1
? 1 8
S

result:

wrong answer Token "S" doesn't correspond to pattern "!|?"