QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#250272 | #7179. Fischer's Chess Guessing Game | kilo_tobo_tarjen# | RE | 0ms | 0kb | C++20 | 2.4kb | 2023-11-13 00:50:56 | 2023-11-13 00:50:56 |
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
vector<int>ve[maxn];
int dep[maxn];
string s[maxn],q[maxn];
vector<string> all;
void getlegal()
{
vector<int> a(8);iota(a.begin(),a.end(),0);
string s="RQKBBNRN";
sort(s.begin(),s.end());
do{
string ss;
for(int i=0;i<8;i++)ss.push_back(s[a[i]]);
bool flag=true;
int g=0,k;
vector<int> v;
for(int i=0;i<8;i++){
if(ss[i]=='K')k=i;
if(ss[i]=='R')v.push_back(i);
if(ss[i]=='B')g+=i;
}
if(g%2==1&&k>v[0]&&k<v[1])all.push_back(ss);
}while(next_permutation(a.begin(),a.end()));
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
}
int f(string s1,string s2){
int res=0;
for(int i=0;i<8;i++)res+=s1[i]==s2[i];
return res;
}
int tot=0;
int dfs(vector<string>&now,int d){
if((int)now.size()==1){
s[++tot]=now[0];
return tot;
}
if(now.empty())return -1;
assert(d<=5);
int id=++tot;
int mi=1e9;
string tt;
for(auto &it:all){
vector<string> p[9];
int g=0;
for(auto &t:now){
int z=f(it,t);
p[z].push_back(t);
g=max((int)p[z].size(),g);
}
if(g<mi){
mi=g;tt=it;
}
}
vector<string> p[9];
for(auto &t:now){
int z=f(tt,t);
p[z].push_back(t);
}
q[id]=tt;
for(int i=0;i<9;i++)ve[id].push_back(dfs(p[i],d+1));
// cout<<"id="<<id<<"\n";
// for(auto it:ve[id])cout<<it<<" ";;cout<<"\n";
return id;
}
void init()
{
getlegal();
dfs(all,1);
}
struct gettime{
clock_t star,ends;
void begin(){
star = clock();
}
void end(){
ends = clock();
cout <<"Running Time : "<<(double)(ends - star)/ CLOCKS_PER_SEC << endl;
}
} tim;
int query(string s){
cout<<s<<endl;
int x;cin>>x;return x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
tim.begin();
init();
string z;
while(cin>>z){
int t;cin>>t;
int now=1;
while(s[now].empty()){
// cout<<"now="<<now<<"\n";
int g=query(q[now]);
now=ve[now][g];
assert(now!=-1);
}
query(s[now]);
}
cin>>z;
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
GAME 1 1 0 2 4 8 END
output:
NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN RKRBBQNN