QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414774#7179. Fischer's Chess Guessing GamepandapythonerRE 1ms3684kbC++202.7kb2024-05-19 17:28:162024-05-19 17:28:17

Judging History

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

  • [2024-05-19 17:28:17]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3684kb
  • [2024-05-19 17:28:16]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


vector<string> good;


void build() {
    good.clear();
    string s = "KQRRBBNN";
    sort(all(s));
    while (1) {
        int rc = 0;
        bool ok = true;
        int wb = 0;
        for (int i = 0; i < 8; i += 1) {
            if (s[i] == 'R') {
                rc += 1;
            }
            if (s[i] == 'K') {
                if (rc != 1) {
                    ok = false;
                }
            }
            if (s[i] == 'B' and i % 2 == 0) {
                wb += 1;
            }
        }
        if (wb != 1) {
            ok = false;
        }
        if (ok) {
            good.push_back(s);
        }
        if (!next_permutation(all(s))) {
            break;
        }
    }
}


int operator&(const string &a, const string &b){
    int rs = 0;
    for(int i = 0; i < min((int)a.size(), (int)b.size()); i += 1){
        if(a[i] == b[i]){
            rs += 1;
        }
    }
    return rs;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    build();
    cerr << good.size() << "\n";
    while(1){
        string aboba;
        cin >> aboba;
        if(aboba == "END"){
            break;
        }
        assert(aboba == "GAME");
        int num;
        cin >> num;
        vector<string> rest = good;
        auto make_move = [&](string s){
            cout << s << endl;
            int x;
            cin >> x;
            if(x == 8){
                return true;
            }
            vector<string> nrest;
            for(auto &t: rest){
                if((s & t) == x){
                    nrest.push_back(t);
                }
            }
            rest.swap(nrest);
            return false;
        };
        auto get_goodness = [&](string s) -> int {
            vector<int> cnt(9);
            for(auto &t: rest){
                cnt[t & s] += 1;
            }
            return *max(all(cnt));
        };
        while(1){
            assert(!rest.empty());
            string s = rest[0];
            int gdns = get_goodness(s);
            for(int itr = 0; itr < 30; itr += 1){
                string f = rest[rnd() % (int)rest.size()];
                int fgdns = get_goodness(f);
                if(fgdns < gdns){
                    s = f;
                    gdns = fgdns;
                }
            }
            if(make_move(s)){
                break;
            }
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

GAME 1
0
1
2
2
8
END

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN

result:

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

Test #2:

score: -100
Runtime Error

input:

GAME 1
0
1
2
2
8
GAME 2
0
1
3
8
GAME 3
0
2
2
1
2
8
GAME 4
1
2
2
1
3
8
GAME 5
0
1
1
4
8
GAME 6
0
2
1
2
8
GAME 7
0
0
4
0
8
GAME 8
1
1
1
2
2
1

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKRBBNQN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKRNBBQ
QNRKRNBB
RKRBBNNQ
BBNNQRKR
BNQBRKRN
BQRKNNRB
BRKRNBQN
NBRKRQBN
RKRBQNBN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNQNB
RKRBNQBN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQRNBB
RKRBNNBQ
BBNNQRKR
NNBBRKRQ
QRK...

result: