QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647584 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | AC ✓ | 200ms | 4032kb | C++20 | 2.5kb | 2024-10-17 14:48:13 | 2024-10-17 14:48:17 |
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 ++) {
string chs; ld cur = 1e18;
if (i == 1) chs = "BBNNRQKR";
else {
for (auto x: cv) {
map<ll, ll> pp; for (auto y: cv) pp[get(x, y)] ++;
ld avg = 0, j = 0; for (auto [x, y]: pp) avg += y, j ++; avg /= pp.size();
ld tmp = 0; for (auto [x, y]: pp) tmp += (ld)(y - avg) * (y - avg) / pp.size();
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: 4ms
memory: 3788kb
input:
GAME 1 1 3 5 4 8 END
output:
BBNNRQKR RKQNBNRB RKNBBRNQ RKBBRNNQ RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 198ms
memory: 3796kb
input:
GAME 1 1 3 5 4 8 GAME 2 0 3 1 1 3 8 GAME 3 0 3 2 1 8 GAME 4 0 3 1 2 8 GAME 5 1 2 4 2 3 8 GAME 6 0 4 5 3 8 GAME 7 0 3 0 8 GAME 8 1 4 5 5 5 8 GAME 9 1 4 4 3 8 GAME 10 0 5 8 GAME 11 2 4 3 2 4 8 GAME 12 1 6 5 5 8 GAME 13 0 4 8 GAME 14 1 3 2 0 8 GAME 15 1 3 3 3 2 8 GAME 16 0 6 4 4 8 GAME 17 1 5 3 3 8 GAM...
output:
BBNNRQKR RKQNBNRB RKNBBRNQ RKBBRNNQ RKRBBQNN BBNNRQKR RKBQNNRB NRBBNKRQ RNBKQRNB RKQRNBBN RKRBBNQN BBNNRQKR RKBQNNRB NRBBNKRQ RNBKQBRN RKRBBNNQ BBNNRQKR RKBQNNRB NRBBNKRQ RNBKQRNB RKRBQNBN BBNNRQKR RKQNBNRB RQKBNNBR NRQBKNBR RBKRQNBN RKRBNQBN BBNNRQKR RKBQNNRB RKRQNBBN RKBRNBQN RKRBNNBQ BBNNRQKR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 181ms
memory: 3732kb
input:
GAME 1 1 5 5 4 8 GAME 2 3 2 4 4 8 GAME 3 2 4 4 8 GAME 4 1 4 1 2 3 8 GAME 5 2 3 3 3 1 8 GAME 6 3 1 3 8 GAME 7 2 5 2 5 8 GAME 8 2 5 3 4 8 GAME 9 3 2 1 4 3 8 GAME 10 2 4 6 4 8 GAME 11 2 4 5 3 8 GAME 12 3 1 3 5 8 GAME 13 2 2 0 0 3 8 GAME 14 1 3 2 2 2 8 GAME 15 1 3 4 3 8 GAME 16 1 2 4 2 8 GAME 17 2 1 1 5...
output:
BBNNRQKR RKQNBNRB RKNBBNRQ RKNRBNQB RKQBBNNR BBNNRQKR NBRQBNKR BNRBKQNR RNBBNQKR RKNBBQNR BBNNRQKR RKNNBBRQ RKBNNBQR RKNBBNQR BBNNRQKR RKQNBNRB RQKNBBRN BNQRKNRB RKBQRNNB RKQBNNBR BBNNRQKR RKNNBBRQ RQKNNBBR RBNKNRBQ RBKNBRQN RKNBQNBR BBNNRQKR NBRQBNKR BRNKNBQR RKNBNQBR BBNNRQKR RKNNBBRQ RBNKBNRQ RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 191ms
memory: 4032kb
input:
GAME 1 0 0 5 6 8 GAME 2 0 0 6 4 8 GAME 3 0 0 5 8 GAME 4 0 2 3 1 8 GAME 5 1 2 1 3 3 8 GAME 6 0 2 3 0 8 GAME 7 0 1 1 2 8 GAME 8 0 0 8 GAME 9 0 1 3 2 8 GAME 10 0 3 2 0 8 GAME 11 0 2 4 3 8 GAME 12 1 1 0 1 8 GAME 13 3 0 5 8 GAME 14 2 0 1 2 3 8 GAME 15 2 1 3 5 8 GAME 16 2 1 3 8 GAME 17 3 0 6 8 GAME 18 3 0...
output:
BBNNRQKR RKBQNNRB NRKRQBBN NRKRBBNQ QRKRBBNN BBNNRQKR RKBQNNRB NRKRQBBN NRKBQRBN NRKRBBQN BBNNRQKR RKBQNNRB NRKRQBBN NRKRBBNQ BBNNRQKR RKBQNNRB NRBKQRNB RNBBKRNQ QRKRBNNB BBNNRQKR RKQNBNRB RQKBNNBR BRQKNRNB NRBKRNQB NRKRBQNB BBNNRQKR RKBQNNRB NRBKQRNB RNBBKRNQ NRKRBNQB BBNNRQKR RKBQNNRB NNRKBBRQ RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 200ms
memory: 3972kb
input:
GAME 1 2 3 4 8 GAME 2 1 2 2 1 4 8 GAME 3 2 4 2 3 2 8 GAME 4 2 2 2 4 8 GAME 5 1 4 1 4 8 GAME 6 3 0 1 4 8 GAME 7 1 1 2 0 2 8 GAME 8 1 1 1 4 2 8 GAME 9 1 1 2 2 0 8 GAME 10 1 3 4 3 4 8 GAME 11 2 3 1 3 8 GAME 12 2 4 1 3 8 GAME 13 1 2 3 3 8 GAME 14 2 2 2 8 GAME 15 2 3 3 8 GAME 16 0 4 2 6 8 GAME 17 0 3 1 8...
output:
BBNNRQKR RKNNBBRQ RQKNNBBR RQNKRBBN BBNNRQKR RKQNBNRB RQKBNNBR NRKBBQRN RKNRQBBN RNQKRBBN BBNNRQKR RKNNBBRQ RKBNNBQR BNRNKBRQ RNKNBQRB RNNKRBBQ BBNNRQKR RKNNBBRQ NRNQKBBR RBNKQRBN RQNKRNBB BBNNRQKR RKQNBNRB RQKNBBRN BNQRKNRB RNQKRNBB BBNNRQKR NBRQBNKR BRKNRBNQ BNNRKQRB RNNKRQBB BBNNRQKR RKQNBNRB QNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 197ms
memory: 3740kb
input:
GAME 1 0 3 4 4 8 GAME 2 0 2 5 2 8 GAME 3 0 3 6 5 8 GAME 4 0 5 2 5 8 GAME 5 0 4 0 5 8 GAME 6 1 2 1 4 8 GAME 7 1 2 0 2 1 8 GAME 8 0 1 5 3 8 GAME 9 1 2 0 1 2 8 GAME 10 1 4 2 1 8 GAME 11 0 3 3 3 8 GAME 12 2 3 0 3 8 GAME 13 2 1 2 4 4 8 GAME 14 3 1 6 4 8 GAME 15 3 1 8 GAME 16 1 0 3 0 8 GAME 17 1 0 5 3 8 G...
output:
BBNNRQKR RKBQNNRB NRBBNKRQ NRBKNRQB QRBKNBRN BBNNRQKR RKBQNNRB NRBKQRNB NQBRKRNB NRBKQBRN BBNNRQKR RKBQNNRB NRBBNKRQ NRBBKNRQ NRBKNBRQ BBNNRQKR RKBQNNRB RKRQBNNB NRBQNKRB QRBKNNRB BBNNRQKR RKBQNNRB RKRQNBBN NQBRKNRB NRBKQNRB BBNNRQKR RKQNBNRB RQKBNNBR BRQKNRNB NRBKNQRB BBNNRQKR RKQNBNRB RQKBNNBR QRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 184ms
memory: 4004kb
input:
GAME 1 1 1 1 3 2 8 GAME 2 2 2 1 2 2 8 GAME 3 2 3 2 3 8 GAME 4 2 2 2 5 8 GAME 5 2 2 4 2 5 8 GAME 6 3 1 1 2 8 GAME 7 0 2 3 6 8 GAME 8 0 2 2 3 1 8 GAME 9 0 2 3 8 GAME 10 1 3 3 4 2 8 GAME 11 0 4 2 5 8 GAME 12 1 3 2 1 2 8 GAME 13 1 1 0 3 2 8 GAME 14 0 1 1 4 8 GAME 15 1 1 1 0 2 8 GAME 16 2 3 4 4 4 8 GAME ...
output:
BBNNRQKR RKQNBNRB QNRKBBNR QBBRNKRN BRKQNBRN RBBQKRNN BBNNRQKR RKNNBBRQ NRNQKBBR NQBNRKRB NBRKBQRN RBBNKRQN BBNNRQKR RKNNBBRQ RQKNNBBR RKBNRNQB RBBNKRNQ BBNNRQKR RKNNBBRQ NRNQKBBR RBNKQRBN RBQNKRBN BBNNRQKR RKNNBBRQ NRNQKBBR QNRNKBBR NBNRKRBQ RBNQKRBN BBNNRQKR NBRQBNKR BRNKNBQR BNRNKQRB RBNNKRBQ BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 182ms
memory: 3632kb
input:
GAME 1 2 1 4 1 2 8 GAME 2 1 2 4 8 GAME 3 3 2 4 3 8 GAME 4 3 1 4 2 8 GAME 5 2 2 6 5 5 8 GAME 6 2 2 8 GAME 7 2 0 2 2 8 GAME 8 3 2 3 2 8 GAME 9 3 2 4 0 8 GAME 10 1 0 1 2 8 GAME 11 1 0 2 6 8 GAME 12 1 0 2 8 GAME 13 2 1 3 2 2 8 GAME 14 1 1 3 2 8 GAME 15 2 1 4 8 GAME 16 2 1 3 1 1 8 GAME 17 1 0 3 8 GAME 18...
output:
BBNNRQKR RKNNBBRQ BRNBKRQN BNRNKRQB BRKBNQRN QRNBKNBR BBNNRQKR RKQNBNRB RQKBNNBR NRQBKNBR BBNNRQKR NBRQBNKR BNRBKQNR RNBBNQKR NRNBKQBR BBNNRQKR NBRQBNKR BRNKNBQR BRKBNQNR QRNNKBBR BBNNRQKR RKNNBBRQ NRNQKBBR NQNRKBBR NRNKQBBR NRQNKBBR BBNNRQKR RKNNBBRQ NRNQKBBR BBNNRQKR RKNNBBRQ NNRBKQBR BRKBQNNR BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 188ms
memory: 3736kb
input:
GAME 1 2 0 2 3 5 8 GAME 2 3 3 3 8 GAME 3 2 0 3 3 8 GAME 4 3 3 5 5 8 GAME 5 2 0 4 1 8 GAME 6 4 4 2 5 8 GAME 7 1 0 3 1 3 8 GAME 8 1 0 3 2 8 GAME 9 1 0 4 8 GAME 10 2 2 5 4 8 GAME 11 2 2 6 8 GAME 12 1 1 3 1 8 GAME 13 1 2 2 2 1 8 GAME 14 2 3 2 3 4 8 GAME 15 2 4 4 1 8 GAME 16 2 4 2 2 4 8 GAME 17 2 4 1 4 4...
output:
BBNNRQKR RKNNBBRQ NNRBKQBR BRKBQNNR NBBRQKNR QBBRKNNR BBNNRQKR NBRQBNKR RBQNKNBR NBBRKQNR BBNNRQKR RKNNBBRQ NNRBKQBR NQBBNRKR NBBRKNQR BBNNRQKR NBRQBNKR RBQNKNBR BBQRKNNR QBNRKNBR BBNNRQKR RKNNBBRQ NNRBKQBR BNRBNKQR NBQRKNBR BBNNRQKR BRNBKQNR BQNBNRKR BBNRKQRN NBNRKQBR BBNNRQKR RKQNBNRB NNRKQBBR NBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 143ms
memory: 3828kb
input:
GAME 1 3 4 1 5 8 GAME 2 4 3 4 8 GAME 3 4 2 5 8 GAME 4 2 0 3 4 8 GAME 5 2 0 4 6 8 GAME 6 2 0 4 8 GAME 7 3 4 2 8 GAME 8 2 1 0 5 8 GAME 9 3 5 4 8 GAME 10 3 3 4 8 GAME 11 2 0 4 4 2 8 GAME 12 3 4 1 4 8 GAME 13 1 1 6 4 8 GAME 14 1 1 4 1 4 8 GAME 15 1 1 4 3 2 8 GAME 16 1 0 4 2 6 8 GAME 17 1 0 4 2 8 GAME 18...
output:
BBNNRQKR NBRQBNKR RQNBBNKR NBBQRKNR BBRQNKNR BBNNRQKR BRNBKQNR NBRNKQBR BBRNQKNR BBNNRQKR BRNBKQNR BBRQNNKR BBRNNKQR BBNNRQKR RKNNBBRQ NNRBKQBR NQBBNRKR BQRBNKNR BBNNRQKR RKNNBBRQ NNRBKQBR BNRBNKQR BNRBQKNR BBNNRQKR RKNNBBRQ NNRBKQBR BNRBNKQR BBNNRQKR NBRQBNKR RQNBBNKR QBRNBKNR BBNNRQKR RKNNBBRQ BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 75ms
memory: 3740kb
input:
GAME 1 3 4 8 GAME 2 2 2 1 0 5 8 GAME 3 4 4 4 4 8 GAME 4 4 2 2 5 8 GAME 5 3 3 4 2 8 GAME 6 3 4 5 2 4 8 GAME 7 3 3 3 1 8 GAME 8 4 5 4 8 GAME 9 5 4 5 8 GAME 10 4 3 2 3 8 GAME 11 4 4 5 4 8 GAME 12 5 3 3 8 GAME 13 2 0 2 4 8 GAME 14 2 0 3 5 4 8 GAME 15 3 3 1 8 GAME 16 3 2 1 6 8 GAME 17 2 1 1 1 3 8 GAME 18...
output:
BBNNRQKR NBRQBNKR RQNBBNKR BBNNRQKR RKNNBBRQ NRNQKBBR NQBNRKRB RBQKBNNR RNQBBNKR BBNNRQKR BRNBKQNR BQNBNRKR BNNBRKQR RNNBBQKR BBNNRQKR BRNBKQNR BBRQNNKR RBNNBKQR RQNNBBKR BBNNRQKR NBRQBNKR RBQNKNBR QBRNNKBR RNQNBBKR BBNNRQKR NBRQBNKR RQNBBNKR BQRBNNKR RBNKBNQR RNNQBBKR BBNNRQKR NBRQBNKR RBQNKNBR NBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed