QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250270 | #7179. Fischer's Chess Guessing Game | kilo_tobo_tarjen# | TL | 133ms | 91432kb | C++20 | 2.4kb | 2023-11-13 00:48:35 | 2023-11-13 00:48:36 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 133ms
memory: 91432kb
input:
GAME 1 1 0 2 4 8 END
output:
NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: -100
Time Limit Exceeded
input:
GAME 1 1 0 2 4 8 GAME 2
output:
NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN RKRBBQNN