QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224133#7179. Fischer's Chess Guessing GamewxhtzdyRE 0ms0kbC++202.5kb2023-10-23 00:03:192023-10-23 00:03:20

Judging History

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

  • [2023-10-23 00:03:20]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-23 00:03:19]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	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*10+ch-'0';ch=getchar();}
	return x*f;
}

int id,root,ncnt,ch[1000005][9],qq[1000005],ans[1000005];
string str[1005];

map<string,bool> val;
//map<int,string> str;

bool is_good(vector<char> f){
	int cnt=0;
	for(int i=0;i<f.size();i++){
		if(f[i]=='R') cnt++;
		if(f[i]=='K') if(cnt!=1) return false;
	}
	int s=0;
	for(int i=0;i<f.size();i++){
		if(f[i]=='B') s+=(i%2);
	}
	if(s!=1) return false;
	return true;
}

int solve(int x,int y){
	string a=str[x],b=str[y];
	int ret=0;
	for(int i=0;i<8;i++) ret+=(a[i]==b[i]?1:0);
	return ret;
}

void gen_vals(){
	vector<char> f;
	f.pb('K');
	f.pb('Q');
	f.pb('R');
	f.pb('R');
	f.pb('B');
	f.pb('B');
	f.pb('N');
	f.pb('N');
	vector<int> perm(8);
	for(int i=0;i<8;i++) perm[i]=i;
	do{
		vector<char> ff;
		for(int i=0;i<8;i++) ff.pb(f[perm[i]]);
		if(!is_good(ff)) continue;
		string s="";
		for(char c:ff) s+=c;
		if(!val[s]){
			val[s]=true;
			str[++id]=s;
		}
	} while(next_permutation(perm.begin(),perm.end()));
}

void dfs(int&nd,vector<int> v,int dep){
	if(v.empty()) return;
	assert(dep<=5);
	nd=++ncnt;
	assert(nd<=500000);
	int bst=1e9;
	for(int query=1;query<=id;query++){
		vector<int> cnt(9,0);
		for(int i:v) cnt[solve(query,i)]++;
		int mx=*max_element(cnt.begin(),cnt.end());
		if(bst>mx) bst=mx,qq[nd]=query;
	}
	if(dep==5) return;
	vector<vector<int>> gr(9);
	for(int i:v) gr[solve(qq[nd],i)].pb(i);
	for(int i=0;i<=8;i++) dfs(ch[nd][i],gr[i],dep+1);
}

int final;

int diff(string a,string b){
	int ret=0;
	for(int i=0;i<8;i++) ret+=(a[i]==b[i]);
	return ret;
}

int prnt(string s){
	cout<<s<<endl;
	int x;
	cin>>x;
	return x;
}

void go(int nd,int dep){
	assert(dep<=6);
	int f=prnt(str[qq[nd]]);
	if(f==8) return;
	go(ch[nd][f],dep+1);
}

int main(){
	gen_vals();
	vector<int> vec;
	for(int i=1;i<=id;i++) vec.pb(i);
	dfs(root,vec,0);
	while(true){
		string s;
		cin>>s;
		if(s[0]=='E') break;
		if(s[0]=='G') cin>>s;
		go(root,1);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

GAME 1
4
3
3
2
3
3

output:

RQKBBNRN
RQKNBRNB
RKQNBNRB
QRKRBNNB
QRKRBBNN
QRKRBBNN

result: