QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224128 | #7179. Fischer's Chess Guessing Game | wxhtzdy | RE | 0ms | 0kb | C++20 | 2.5kb | 2023-10-23 00:02:32 | 2023-10-23 00:02:32 |
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);
if(dep==5){
ans[nd]=v[0];
return;
}
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;
}
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
output:
RQKBBNRN RQKNBRNB RKQNBNRB QRKRBNNB QRKRBBNN