QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699674#9537. Chinese Chessucup-team3586#TL 0ms0kbC++233.0kb2024-11-02 10:21:532024-11-02 10:21:53

Judging History

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

  • [2024-11-02 10:21:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-02 10:21:53]
  • 提交

answer

#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
// #define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[6][10][9][10][9];
vector<pair<int,int>> op[6];
#define xqw vector<pair<int,pair<int,int>>>
const string str="JSCMXB";
// map<xqw,bool> mp;
map<xqw,pair<int,int>> mp;
pair<int,int> F(xqw &f,int req)
{
	int c=f[0].first;
	bool ok=1;
	for(auto i:f) ok&=(i.first==c);
	if(ok) return {0,0};
	if(req==0) return {-1,-1};
	if(mp.count(f)) return mp[f];
	for(int i=0; i<10; ++i)
		for(int j=0; j<9; ++j)
		{
			xqw t[103];
			for(auto [p,_]:f)
			{
				auto [q,r]=_;
				t[a[p][q][r][i][j]+1].push_back({p,_});
			}
			bool gg=0;
			for(int k=0; k<100; ++k)
				if(t[k].size()==f.size()) gg=1;
			if(gg) continue;
			int cur=1;
			for(int k=0; k<100; ++k)
				if(!t[k].empty())
					cur&=F(t[k],req-1).first!=-1;
			// ans=min(ans,cur+1);
			if(cur) return mp[f]={i,j};
		}
	return mp[f]={-1,-1};
	// return mp[f]=ans;
}
int _o=5,_x,_y;
void dfs(xqw &f)
{
	assert(!f.empty());
	int c=f[0].first;
	bool ok=1;
	for(auto i:f) ok&=(i.first==c);
	if(ok)
	{
		printf("! ");
		putchar(str[c]);
		fflush(stdout);
		exit(0);
	}
	auto [i,j]=mp[f];
	// assert(i!=-1);
	printf("? %d %d\n",i,j);fflush(stdout);
	int res=read();
	// int res=a[_o][_x][_y][i][j];
	xqw nxt;
	for(auto [p,_]:f)
	{
		auto [q,r]=_;
		if(a[p][q][r][i][j]==res)
			nxt.push_back({p,_});
	}
	dfs(nxt);
	return ;
}
signed main()
{
	memset(a,-1,sizeof(a));
	op[0]={{1,0},{-1,0},{0,1},{0,-1}};
	op[1]={{1,1},{-1,-1},{1,-1},{-1,1}};
	for(int i=1; i<=9; ++i)
		op[2].push_back({i,0}),
		op[2].push_back({-i,0}),
		op[2].push_back({0,i}),
		op[2].push_back({0,-i});
	op[3]={{2,1},{2,-1},{-2,1},{-2,-1},{1,-2},{1,2},{-1,-2},{-1,2}};
	op[4]={{2,2},{-2,-2},{-2,2},{2,-2}};
	op[5]={{1,0},{0,-1},{0,1}};
	for(int d=0; d<6; ++d)
		for(int i=0; i<10; ++i)
			for(int j=0; j<9; ++j)
			{
				a[d][i][j][i][j]=0;
				queue<pair<int,int>> q;
				q.push({i,j});
				while(!q.empty())
				{
					auto [x,y]=q.front();q.pop();
					if(d==5&&x<=4)
					{
						a[d][i][j][x+1][y]=a[d][i][j][x][y]+1;
						q.push({x+1,y});
						continue;
					}
					for(auto [dx,dy]:op[d])
					{
						if(a[d][i][j][x+dx][y+dy]==-1
						&&0<=x+dx&&x+dx<10
						&&0<=y+dy&&y+dy<9)
						a[d][i][j][x+dx][y+dy]=a[d][i][j][x][y]+1,
						q.push({x+dx,y+dy});
					}
				}
			}
	vector<pair<int,pair<int,int>>> vec;
	int TTT=read();
	int B=rand()%TTT;
	for(int T=TTT; T--;)
	{
		int x=read(),y=read();
		if(B==T) _x=x,_y=y;
		for(int i=0; i<6; ++i)
			vec.push_back({i,{x,y}});
	}
	// printf("%d %d %d\n",_o,_x,_y);
	int T=1;
	while(1)
	{
		mp.clear();
		if(F(vec,T).first!=-1) break;
		++T;
	}
	dfs(vec);
	// printf("%d\n",T);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1
9 0

output:

? 1 8

result: