QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#250270#7179. Fischer's Chess Guessing Gamekilo_tobo_tarjen#TL 133ms91432kbC++202.4kb2023-11-13 00:48:352023-11-13 00:48:36

Judging History

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

  • [2023-11-13 00:48:36]
  • 评测
  • 测评结果:TL
  • 用时:133ms
  • 内存:91432kb
  • [2023-11-13 00:48:35]
  • 提交

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: 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

result: