QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#707530#9537. Chinese Chessucup-team4938TL 0ms0kbC++145.6kb2024-11-03 16:24:432024-11-03 16:24:44

Judging History

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

  • [2024-11-03 16:24:44]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-03 16:24:43]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

char opt[7];
int p;
const int maxn=95;
int n=10,m=9;
pii a[maxn];
queue<int> q;
int dis[6][maxn][maxn];
int id(int u,int v){return u*m+v;}
pii get(int id){return {id/m,id%m};}
int fxs[4][2]={{1,-1},{1,1},{-1,1},{-1,-1}};
int fxm[8][2]={{1,-2},{1,2},{-1,2},{-1,-2},{2,-1},{2,1},{-2,1},{-2,-1}};
int fxx[4][2]={{2,-2},{2,2},{-2,2},{-2,-2}};
vector<pii> op1[25],op2[25];
int op[25];
bool check1(int s1,vector<pii> que){
	for(int i=0;i<=20;i++)op[i]=-1;
	bool fl=1;
	for(auto[i,j]:que){
		int s=id(a[i].fi,a[i].se);
		int d=dis[j][s][s1];
		if(op[d]!=-1&&op[d]!=j){fl=0;break;}
		op[d]=j;
	}
	return fl;
}
int ans1[maxn],ans2[maxn];
bool check2(int s1,vector<pii> que){
	for(int i=0;i<=20;i++)op1[i].clear();
	for(auto[i,j]:que){
		int s=id(a[i].fi,a[i].se);
		int d=dis[j][s][s1];
		op1[d].pb({i,j});
	}
	bool fl=1;
	for(int i=0;i<=20;i++)if(op1[i].size()){
		bool fl1=0;
		for(int s=0;s<n*m;s++){
			if(check1(s,op1[i])){
				ans1[i]=s;
				fl1=1;break;
			}
		}
		if(!fl1){fl=0;break;}
	}
	return fl;
}
bool check3(int s1,vector<pii> que){
	for(int i=0;i<=20;i++)op2[i].clear();
	for(auto[i,j]:que){
		int s=id(a[i].fi,a[i].se);
		int d=dis[j][s][s1];
		op2[d].pb({i,j});
	}
	bool fl=1;
	for(int i=0;i<=20;i++)if(op2[i].size()){
		bool fl1=0;
		for(int s=0;s<n*m;s++){
			if(check2(s,op2[i])){
				// if(s1==0)cout<<i<<" "<<s<<" "<<op2[i].size()<<"\n";
				ans2[i]=s;
				fl1=1;break;
			}
		}
		if(!fl1){fl=0;break;}
	}
	return fl;
}
void work(){
	p=read();
	for(int i=1;i<=n;i++)a[i]={read(),read()};
	opt[0]='J',opt[1]='S',opt[2]='C',opt[3]='M',opt[4]='X',opt[5]='B';
	mems(dis,-1);mems(op,-1);
	for(int s=0;s<n*m;s++){
		for(int t=0;t<n*m;t++){
			int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
			dis[0][s][t]=abs(u-nx)+abs(v-ny);
		}
		dis[1][s][s]=0,q.push(s);
		while(!q.empty()){
			int ss=q.front();q.pop();
			int u=get(ss).fi,v=get(ss).se;
			for(int i=0;i<4;i++){
				int nx=u+fxs[i][0],ny=v+fxs[i][1];
				if(nx<0||ny<0||nx>=n||ny>=m||dis[1][s][id(nx,ny)]!=-1)continue;
				dis[1][s][id(nx,ny)]=dis[1][s][ss]+1,q.push(id(nx,ny));
			}
		}
		for(int t=0;t<n*m;t++){
			int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
			dis[2][s][t]=(u!=nx)+(v!=ny);
		}
		dis[3][s][s]=0,q.push(s);
		while(!q.empty()){
			int ss=q.front();q.pop();
			int u=get(ss).fi,v=get(ss).se;
			for(int i=0;i<8;i++){
				int nx=u+fxm[i][0],ny=v+fxm[i][1];
				if(nx<0||ny<0||nx>=n||ny>=m||dis[3][s][id(nx,ny)]!=-1)continue;
				dis[3][s][id(nx,ny)]=dis[3][s][ss]+1,q.push(id(nx,ny));
			}
		}
		dis[4][s][s]=0,q.push(s);
		while(!q.empty()){
			int ss=q.front();q.pop();
			int u=get(ss).fi,v=get(ss).se;
			for(int i=0;i<4;i++){
				int nx=u+fxx[i][0],ny=v+fxx[i][1];
				if(nx<0||ny<0||nx>=n||ny>=m||dis[4][s][id(nx,ny)]!=-1)continue;
				dis[4][s][id(nx,ny)]=dis[4][s][ss]+1,q.push(id(nx,ny));
			}
		}
		for(int t=0;t<n*m;t++){
			int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
			if(nx<u)dis[5][s][t]=-1;
			else if(nx>4)dis[5][s][t]=abs(u-nx)+abs(v-ny);
			else{
				if(v==ny)dis[5][s][t]=abs(nx-u);
				else dis[5][s][t]=-1;
			}
		}
	}
	for(int i=0;i<6;i++){
		for(int s=0;s<=n*m;s++){
			for(int t=0;t<=n*m;t++)if(dis[i][s][t]==-1)dis[i][s][t]=20;
		}
	}
	vector<pii> que;
	for(int i=1;i<=p;i++){
		for(int j=0;j<6;j++)que.pb({i,j});
	}
	for(int s=0;s<n*m;s++){
		if(check1(s,que)){
			// cout<<s<<"\n";
			cout<<"1"<<endl;
			int u=get(s).fi,v=get(s).se;
			cout<<"? "<<u<<" "<<v<<endl;
			int x=read();
			if(x==-1)x=20;
			cout<<"! "<<opt[op[x]]<<endl;
			return ;
		}
	}
	for(int s=0;s<n*m;s++){
		if(check2(s,que)){
			// cout<<s<<"\n";
			// for(int i=0;i<=20;i++)cout<<ans1[s]<<" ";cout<<"\n";
			cout<<"2"<<endl;
			int u=get(s).fi,v=get(s).se;
			cout<<"? "<<u<<" "<<v<<endl;
			int x=read();
			if(x==-1)x=20;
			que=op1[x];
			for(int ss=0;ss<n*m;ss++){
				if(check1(ss,que)){
					int u=get(ss).fi,v=get(ss).se;
					cout<<"? "<<u<<" "<<v<<endl;
					int x=read();
					if(x==-1)x=20;
					// cout<<x<<" "<<op[x]<<"\n";
					cout<<"! "<<opt[op[x]]<<endl;
					return ;
				}
			}
			return ;
		}
	}
	// cout<<que.size()<<"\n";
	for(int s=0;s<n*m;s++){
		if(check3(s,que)){
			// cout<<s<<"\n";
			// for(int i=0;i<=20;i++)cout<<ans2[i]<<" ";cout<<"\n";
			cout<<"3"<<endl;
			int u=get(s).fi,v=get(s).se;
			cout<<"? "<<u<<" "<<v<<endl;
			int x=read();
			if(x==-1)x=20;
			que=op2[x];
			for(int sss=0;sss<n*m;sss++){
				if(check2(sss,que)){
					int u=get(sss).fi,v=get(sss).se;
					cout<<"? "<<u<<" "<<v<<endl;
					int x=read();
					if(x==-1)x=20;
					que=op1[x];
					for(int ss=0;ss<n*m;ss++){
						if(check1(ss,que)){
							int u=get(ss).fi,v=get(ss).se;
							cout<<"? "<<u<<" "<<v<<endl;
							int x=read();
							if(x==-1)x=20;
							cout<<"! "<<opt[op[x]]<<endl;
							return ;
						}
					}
				}
			}
		}
	}
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

1
9 0

output:


result: