QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345266#7179. Fischer's Chess Guessing Gameinstallb#TL 27ms3728kbC++143.2kb2024-03-06 18:43:492024-03-06 18:43:50

Judging History

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

  • [2024-03-06 18:43:50]
  • 评测
  • 测评结果:TL
  • 用时:27ms
  • 内存:3728kb
  • [2024-03-06 18:43:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int N = 800005;

vector <string> G,iG;
map <string,int> mp; int tot = 0;

void init1(){
    string s = "BBKNNQRR";
    do{
        int pk; vector <int> pb,pr;
        for(int i = 0;i < 8;i ++){
            if(s[i] == 'B') pb.push_back(i);
            if(s[i] == 'R') pr.push_back(i);
            if(s[i] == 'K') pk = i;
        }
        if((pb[0] & 1) == (pb[1] & 1)) continue;
        if(!(pr[0] < pk && pk < pr[1])) continue;
        if(mp.find(s) != mp.end()) continue;
        mp[s] = tot ++;
        G.push_back(s);
    }while(next_permutation(s.begin(),s.end()));
}

mt19937 rnd(998244353);
string SS;

int calc(string x,string y){ int r = 0; for(int i = 0;i < 8;i ++) if(x[i] == y[i]) r ++; return r; }

void solve(){
    vector <string> H;
    G = iG;
    string lis[6];
    for(int ti = 0;ti < 5;ti ++){
        db anss = 0;
        if(G.size() == 1) break;
        string cur;
        for(int x = 0;x < G.size();x ++){
            map <int,int> chk;
            for(int i = 0;i < G.size();i ++) chk[calc(G[i],G[x])] ++;
            db mx = 0;
            for(auto it = chk.begin();it != chk.end();it ++){
                db val = 1.0 * it->second / G.size();
                mx += val * log(1.0 / val);
            }
            if(mx > anss){
                anss = mx;
                cur = G[x];
            }
        }
        cout << cur << endl;
        int x;
        cin >> x;
        // x = calc(cur,SS);
        if(x == 8) return;
        for(int i = 0;i < G.size();i ++) if(calc(cur,G[i]) == x) H.push_back(G[i]);
        G.swap(H); H.clear();
        lis[ti] = cur;
        // cout << x << ' ' << cur << ' ' << SS << ' ' << G.size() << ' ' << G[0] << ' ' << G[1] << endl;
        // cout << ti << ' ' << anss << '\n';
    }
    cout << G[0] << endl;
    int x;
    cin >> x;
    // x = calc(G[0],SS);
    // cout << x << endl;
    // if(x != 8) cout << SS << endl;
    // assert(x == 8);
    // cout << SS << endl;
    // for(int i = 0;i < 6;i ++) cout << lis[i] << '\n';
}

// void countt(){
//     string lis[6];
//     for(int i = 0;i < 6;i ++) cin >> lis[i];
//             map <vector <int>,int> chk;
//             for(int i = 0;i < tot;i ++){
//                 vector <int> vec;
//                 for(int j = 0;j < 6;j ++){
//                     int cnt = 0;
//                     for(int k = 0;k < 8;k ++) if(G[i][k] == lis[j][k]) cnt ++;
//                     vec.push_back(cnt);
//                 }
//                 // cout << G[i] << " : "; for(auto u : vec) cout << u << ' '; cout << endl;
//                 chk[vec] = 1;
//             }
//     cout << chk.size() << '\n';
// }

int main(){
    ios::sync_with_stdio(false);
    init1();
    iG = G;
    // for(auto s : G) cout << s << ' ';
    // cout << tot << endl;
    // solve2();
    // countt();
    // int id = 0;
    // for(auto x : iG){
    //     SS = x;
    //     // cout << ++ id << endl;
    //     solve();
    // }
    string str;
    while(cin >> str){
        if(str == "END") break;
        int x; cin >> x;
        // cin >> SS;
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 27ms
memory: 3728kb

input:

GAME 1
2
3
1
1
2
8
END

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 6 (1 test case)

Test #2:

score: -100
Time Limit Exceeded

input:

GAME 1
2
3
1
1
2
8
GAME 2
1
4
0
6
8
GAME 3
1
3
6
8
GAME 4
1
3
3
0
8
GAME 5
3
3
3
8
GAME 6
2
5
3
4
8
GAME 7
1
3
4
4
5
8
GAME 8
2
2
3
1
8
GAME 9
2
2
2
1
1
8
GAME 10
1
2
0
8
GAME 11
3
3
4
2
8
GAME 12
2
3
0
3
6
8
GAME 13
2
3
2
3
3
8
GAME 14
2
4
3
3
8
GAME 15
3
4
3
2
8
GAME 16
2
4
6
8
GAME 17
2
5
6
8
GAM...

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN
RBBNNQKR
RNQBBKRN
BNQNRKRB
RKNBBRQN
RKRBBNQN
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RKRBBNNQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
NBNRBKRQ
RKRBQNBN
RBBNNQKR
RKBNQBRN
RKBQNRNB
RKRBNQBN
RBBNNQKR
RKNBQNBR
RKNNQRBB
RKBBQNRN
RKRBNNBQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNKRBBNQ
RKN...

result: