QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647130#7179. Fischer's Chess Guessing Gameno_RED_no_DEADRE 20ms3664kbC++202.3kb2024-10-17 11:55:522024-10-17 11:55:57

Judging History

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

  • [2024-10-17 11:55:57]
  • 评测
  • 测评结果:RE
  • 用时:20ms
  • 内存:3664kb
  • [2024-10-17 11:55:52]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;
const ll B = 8;

vector<string> v;
set<string> s;
string cur;

void backtrack(ll pos, ll r, ll n, ll b, ll k, ll q) {
    if (pos > B) {
        ll r1 = 1e18, r2 = -1e18, b1 = 1e18, b2 = -1e18, k1 = -1e18;
        for (ll i = 0; i < cur.size(); i ++) {
            if (cur[i] == 'R') r1 = min(r1, i), r2 = max(r2, i);
            if (cur[i] == 'B') b1 = min(b1, i), b2 = max(b2, i);
            if (cur[i] == 'K') k1 = max(k1, i);
        }
        if (b1 % 2 == b2 % 2) return;
        if (r1 > k1 || r2 < k1) return;
        s.insert(cur);
        return;
    }
    if (r < 2) cur += 'R', backtrack(pos + 1, r + 1, n, b, k, q), cur.pop_back();
    if (n < 2) cur += 'N', backtrack(pos + 1, r, n + 1, b, k, q), cur.pop_back();
    if (b < 2) cur += 'B', backtrack(pos + 1, r, n, b + 1, k, q), cur.pop_back();
    if (k < 1) cur += 'K', backtrack(pos + 1, r, n, b, k + 1, q), cur.pop_back();
    if (q < 1) cur += 'Q', backtrack(pos + 1, r, n, b, k, q + 1), cur.pop_back();
}

ll get(string &a, string &b) {
    ll res = 0; 
    for (int i = 0; i < a.size(); i ++)
        if (a[i] == b[i]) res ++;
    return res;
}

void doTest(ll testID) {
    backtrack(1, 0, 0, 0, 0, 0);
    for (auto x: s) v.push_back(x);

    while (true) {
        string s; ll num; cin >> s; if (s == "END") return; cin >> num;
        
        vector<string> cv = v; 
        for (int i = 1;; i ++) {
            assert(i <= 6);
            string chs; ll cur = -1;
            for (auto x: cv) {
                ll tmp = 1e18;
                for (auto y: cv)
                    tmp = min(tmp, get(x, y));
                if (tmp > cur) cur = tmp, chs = x;
            }

            cout << chs << endl;
            ll req; cin >> req; if (req == 8) break;
            
            vector<string> nv;
            for (auto x: cv)
                if (get(x, chs) == req) 
                    nv.push_back(x);
            cv = nv;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    // cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(_);
}

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 3664kb

input:

GAME 1
0
1
2
3
8
END

output:

BBNNQRKR
NNBBRKRQ
RKBRNNQB
NRKRBQNB
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
3
8
GAME 2
0
1
4
3
8
GAME 3
0
2
4
2
8
GAME 4
1
2
2
3
1
8
GAME 5
0
1
3
3
8
GAME 6
0
2
3
1
4
3

output:

BBNNQRKR
NNBBRKRQ
RKBRNNQB
NRKRBQNB
RKRBBQNN
BBNNQRKR
NNBBRKRQ
RKBRNNQB
NRKRBNQB
RKRBBNQN
BBNNQRKR
NNBBRKRQ
RQKBBNRN
NQRKBBRN
RKRBBNNQ
BBNNQRKR
BNQBRKRN
BQRKNNRB
RBKQBNRN
QRNKBBRN
RKRBQNBN
BBNNQRKR
NNBBRKRQ
RKBRNNQB
NRKRNQBB
RKRBNQBN
BBNNQRKR
NNBBRKRQ
RQKBBNRN
QNRKBBRN
RKBQNNRB
RNKQRNBB

result: