QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647154 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | RE | 1ms | 3948kb | C++20 | 2.7kb | 2024-10-17 12:07:45 | 2024-10-17 12:07:53 |
Judging History
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, me = -1;
if (i == 1) chs = cv[0];
else {
for (auto x: cv) {
ll tmp = 1e18; for (auto y: cv) tmp = min(tmp, get(x, y));
if (tmp > cur) cur = tmp, chs = x;
}
for (auto x: cv) {
ll tmp = 1e18; for (auto y: cv) tmp = min(tmp, get(x, y));
if (tmp == cur) {
ll e = 0; for (auto y: cv) e += get(x, y) * log2(get(x, y)) * log2(get(x, y));
if (e > me) me = e, 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;
// cout << cv.size() << endl;
}
}
}
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: 1ms
memory: 3948kb
input:
GAME 1 0 1 4 1 8 END
output:
BBNNQRKR NNBBRKRQ RNKRBQNB NRKRBNQB 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 4 1 8 GAME 2 0 1 2 8 GAME 3 0 2 4 3 2 8 GAME 4 1 2 2 2 2 1
output:
BBNNQRKR NNBBRKRQ RNKRBQNB NRKRBNQB RKRBBQNN BBNNQRKR NNBBRKRQ RNKRBQNB RKRBBNQN BBNNQRKR NNBBRKRQ RQKBBNRN NQRKBNRB RNQKBBRN RKRBBNNQ BBNNQRKR BNQBRKRN BQRKNNRB RQBNKBRN RNQKNBBR BRKRNBQN