QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196940#7179. Fischer's Chess Guessing Gameucup-team1430TL 0ms0kbC++202.7kb2023-10-02 04:46:202023-10-02 04:46:20

Judging History

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

  • [2023-10-02 04:46:20]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-02 04:46:20]
  • 提交

answer

#include <bits/stdc++.h>

#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define sws cin.tie(0)->sync_with_stdio(false);

const int N = 0;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

bool is_valid(vector<char> s) {
    int n = s.size();
    bool ok = true;
    int bishop = -1, rook = -1;
    for (int i=0;i<n;i++) {
        auto c = s[i];
        if (c == 'B') {
            if (bishop == -1) bishop = i;
            else ok &= ((i - bishop) % 2 == 1);
        } else if (c == 'R') {
            if (rook == -1) rook = i;
            else rook = -1;
        } else if (c == 'K') {
            ok &= (rook != -1);
        }
    }

    return ok;
}

auto dist = [](vector<char> &a, vector<char> &b) {
    int qnt = 0;
    int n = a.size();
    for (int i=0;i<n;i++) {
        if (a[i] != b[i]) qnt ++;
    }
    return qnt;
};

void solve() {


    vector<char> pos = {'K', 'Q', 'R', 'R', 'N', 'N', 'B', 'B'};
    sort(pos.begin(), pos.end());
    vector<vector<char>> p_ini;
    do {
        p_ini.push_back(pos);
    } while (next_permutation(pos.begin(), pos.end()));

    vector<vector<char>> p;
    for (auto pi: p_ini) if (is_valid(pi)) p.push_back(pi);
    p_ini = p;

    auto print = [&](vector<char> &x) {
        for (auto c: x) cout << c;
        cout << endl;
    };


    auto choose = [&](vector<vector<char>> &p) {
        int n = p_ini.size();
        int m = p.size();
        int id = 0, mx = INF;
        for (int i=0;i<n;i++) {
            vector<int> dists(10, 0);
            for (int j=0;j<m;j++) {
                int d = dist(p_ini[i], p[j]);
                dists[d] ++;
            }
            int dmax = 0;
            for (auto d: dists) dmax = max(dmax, d);
            if (dmax <= mx) {
                id = i; mx = dmax;
            }
        }

        return id;
    };


    int it = 6;
    while (it --) {
        if (p.size() == 1) {
            print(p[0]);
            int x; cin >> x; assert(x == 8);
            return;
        }
        int id = choose(p);
        print(p_ini[id]);
        cout.flush();
        int x; cin >> x;
        if (x == 8) { return; }

        vector<vector<char>> p2;

        for (auto pi: p) {
            if (dist(p_ini[id], pi) == 8 - x) {
                p2.push_back(pi);
            }
        }

        swap(p, p2);
    }
}

int main() {
    #ifndef LOCAL
        sws;
    #endif

    string s; int t;
    while (cin >> s >> t) {
        if (s == "END") return 0;
        solve();
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

GAME 1
3
1
4
1
1

output:

RQKNBBRN
NRNKBBQR
RKBRNQNB
RQNKNBBR
RQNNKRBB

result: