QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710490 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | AC ✓ | 153ms | 3952kb | C++20 | 2.9kb | 2024-11-04 20:04:45 | 2024-11-04 20:04:45 |
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;
ll pp[N];
vector<string> v;
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;
v.push_back(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;
}
// NX1: Định lý Phong: càng gần trung tâm x thì càng nhiều trường hợp
// Lần thử 1: Đỉnh càng lớn thì càng tệ
void doTest(ll testID) {
backtrack(1, 0, 0, 0, 0, 0);
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 = "RNKBRQBN";
if (i != 1) {
ll mx = 1e18;
for (auto x: cv) {
// Reset
for (int j = 0; j <= 8; j ++) pp[j] = 0;
// Lập cái đồ thị
for (auto y: cv) pp[get(x, y)] ++;
// Tính phương sai
ll avg = 0, v = 0;
for (int j = 0; j <= 8; j ++) avg += pp[j]; avg /= 9;
for (int j = 0; j <= 8; j ++) v += (pp[j] - avg) * (pp[j] - avg);
// Chọn đồ thị có phương sai bé nhất
if (v < mx) mx = v, 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: 1ms
memory: 3628kb
input:
GAME 1 4 2 3 3 8 END
output:
RNKBRQBN RBKNQRBN BRKBNQRN RNKBBNRQ RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 128ms
memory: 3684kb
input:
GAME 1 4 2 3 3 8 GAME 2 3 2 3 1 8 GAME 3 2 2 6 8 GAME 4 4 4 4 3 8 GAME 5 5 4 8 GAME 6 3 2 1 3 3 8 GAME 7 2 4 3 8 GAME 8 2 5 5 8 GAME 9 1 3 2 6 8 GAME 10 1 1 1 3 3 8 GAME 11 2 3 0 3 8 GAME 12 1 2 0 8 GAME 13 3 1 1 3 8 GAME 14 3 2 2 3 8 GAME 15 2 4 2 8 GAME 16 2 2 3 1 8 GAME 17 2 4 4 8 GAME 18 3 1 0 2...
output:
RNKBRQBN RBKNQRBN BRKBNQRN RNKBBNRQ RKRBBQNN RNKBRQBN RNBBQKNR RNKNBRQB RQKNNBBR RKRBBNQN RNKBRQBN RKBNQBRN RKQBBNNR RKRBBNNQ RNKBRQBN RBKNQRBN RQNBKRBN RQKRNBBN RKRBQNBN RNKBRQBN RNKRNQBB RKRBNQBN RNKBRQBN RNBBQKNR RNKNBRQB RKNRQBBN RBNKNQBR RKRBNNBQ RNKBRQBN RKBNQBRN RKBBQNNR RKRQBBNN RNKBRQBN RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 68ms
memory: 3676kb
input:
GAME 1 2 2 8 GAME 2 3 4 1 8 GAME 3 2 2 6 5 8 GAME 4 3 3 1 2 8 GAME 5 3 4 2 4 8 GAME 6 4 2 3 2 8 GAME 7 1 4 2 6 8 GAME 8 1 3 3 5 8 GAME 9 1 4 2 8 GAME 10 2 4 3 3 1 8 GAME 11 2 3 1 3 1 8 GAME 12 2 5 3 8 GAME 13 4 4 2 3 8 GAME 14 3 1 4 1 8 GAME 15 2 1 2 3 8 GAME 16 4 6 8 GAME 17 5 6 8 GAME 18 3 1 1 8 G...
output:
RNKBRQBN RKBNQBRN RKQBBNNR RNKBRQBN RNBBQKNR RNBKQBRN RKNBBQNR RNKBRQBN RKBNQBRN RKQBBNNR RKRBBNNQ RKNBBNQR RNKBRQBN RNBBQKNR RNBQKBRN NNRBBQKR RKQBNNBR RNKBRQBN RNBBQKNR RNBKQBRN RNQBBNKR RKNBQNBR RNKBRQBN RBKNQRBN BRKBNQRN RNKBBNRQ RKNBNQBR RNKBRQBN RQBNNBKR BNRQNBKR RKNNBBQR RKQNBBNR RNKBRQBN RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 119ms
memory: 3952kb
input:
GAME 1 2 2 2 4 1 8 GAME 2 2 2 1 8 GAME 3 1 1 0 1 3 8 GAME 4 1 0 1 2 8 GAME 5 2 0 1 4 8 GAME 6 1 0 0 8 GAME 7 3 0 3 4 8 GAME 8 3 1 4 3 8 GAME 9 2 1 2 8 GAME 10 2 0 1 5 8 GAME 11 2 1 1 4 1 8 GAME 12 3 0 2 8 GAME 13 5 2 5 3 8 GAME 14 4 2 5 2 8 GAME 15 3 2 1 0 8 GAME 16 3 1 3 3 8 GAME 17 3 0 3 8 GAME 18...
output:
RNKBRQBN RKBNQBRN RKQBBNNR QRNBBKRN RNNQBKRB QRKRBBNN RNKBRQBN RKBNQBRN RKQBBNNR NRKRBBQN RNKBRQBN RQBNNBKR BBRNQKRN QRNKNRBB RKQRBNNB NRKRBBNQ RNKBRQBN RQBNNBKR BBRKQRNN NNRQBKRB QRKRBNNB RNKBRQBN RKBNQBRN QNNBBRKR NRKQNRBB NRKRBQNB RNKBRQBN RQBNNBKR BBRKQRNN NRKRBNQB RNKBRQBN RNBBQKNR NQRKRBBN BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 142ms
memory: 3708kb
input:
GAME 1 4 3 3 2 8 GAME 2 5 3 3 8 GAME 3 4 2 0 8 GAME 4 3 1 0 6 8 GAME 5 4 2 0 5 8 GAME 6 5 5 8 GAME 7 2 4 4 2 8 GAME 8 2 3 3 1 2 8 GAME 9 1 3 0 6 4 8 GAME 10 2 2 4 3 4 8 GAME 11 2 2 2 3 8 GAME 12 1 1 1 3 8 GAME 13 3 1 2 5 8 GAME 14 3 2 2 4 8 GAME 15 2 1 5 8 GAME 16 1 4 1 2 8 GAME 17 2 3 1 4 8 GAME 18...
output:
RNKBRQBN RBKNQRBN RNKQBBRN RNBBKRQN RQNKRBBN RNKBRQBN RNKRNQBB RNBBKQRN RNQKRBBN RNKBRQBN RBKNQRBN BRKBNQRN RNNKRBBQ RNKBRQBN RNBBQKNR NRKBBRQN RBNKRNBQ RQNKRNBB RNKBRQBN RBKNQRBN BRKBNQRN RNNKRBBQ RNQKRNBB RNKBRQBN RNKRNQBB RNNKRQBB RNKBRQBN RKBNQBRN RKBBQNNR RKRNQNBB RBBKQRNN RNKBRQBN RKBNQBRN NBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 135ms
memory: 3720kb
input:
GAME 1 1 3 1 5 8 GAME 2 1 2 4 5 8 GAME 3 0 0 6 8 GAME 4 0 1 1 3 4 8 GAME 5 0 2 4 8 GAME 6 1 2 3 2 8 GAME 7 1 1 2 1 2 8 GAME 8 1 1 2 0 8 GAME 9 0 0 8 GAME 10 0 1 0 4 8 GAME 11 0 1 1 6 8 GAME 12 1 0 1 4 8 GAME 13 0 2 2 3 8 GAME 14 0 3 5 8 GAME 15 0 2 3 4 8 GAME 16 0 1 4 6 8 GAME 17 0 2 1 2 8 GAME 18 0...
output:
RNKBRQBN RQBNNBKR NNQRBBKR BQRKNBRN QRBKNBRN RNKBRQBN RQBNNBKR NRBBQKNR NRBKRBNQ NRBKQBRN RNKBRQBN BBRNQNKR NRNKBBRQ NRBKNBRQ RNKBRQBN BBRNQNKR NQBRKBNR NRQNBKRB BRQKNRNB QRBKNNRB RNKBRQBN BBRNQNKR BRNQKNRB NRBKQNRB RNKBRQBN RQBNNBKR NRBBQKNR NBRQNKBR NRBKNQRB RNKBRQBN RQBNNBKR BBRNQKRN BBNRKQNR BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 122ms
memory: 3948kb
input:
GAME 1 2 3 4 3 8 GAME 2 2 4 2 2 8 GAME 3 1 3 0 8 GAME 4 3 1 2 6 8 GAME 5 3 1 2 8 GAME 6 2 2 1 0 8 GAME 7 3 4 3 2 8 GAME 8 4 3 3 8 GAME 9 3 5 3 8 GAME 10 1 4 0 8 GAME 11 2 2 2 0 8 GAME 12 2 3 1 3 8 GAME 13 4 4 8 GAME 14 5 3 5 8 GAME 15 4 3 2 5 8 GAME 16 2 2 1 0 6 8 GAME 17 3 2 5 3 8 GAME 18 3 2 4 4 8...
output:
RNKBRQBN RKBNQBRN NBBQRKRN RNBQNKRB RBBQKRNN RNKBRQBN RKBNQBRN RKBBQNNR RKRNNBBQ RBBNKRQN RNKBRQBN RQBNNBKR NNQRBBKR RBBNKRNQ RNKBRQBN RNBBQKNR NRKBBRQN RBNQKRBN RBQNKRBN RNKBRQBN RNBBQKNR NRKBBRQN RBNQKRBN RNKBRQBN RKBNQBRN RKQBBNNR NRKRBBQN RBNNKRBQ RNKBRQBN RNBBQKNR RNBKQBRN RNNBBKRQ RQBBKRNN RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 153ms
memory: 3704kb
input:
GAME 1 2 0 4 4 8 GAME 2 2 0 2 4 6 8 GAME 3 3 2 0 8 GAME 4 1 3 2 3 8 GAME 5 1 3 4 3 8 GAME 6 1 2 3 4 3 8 GAME 7 1 0 6 8 GAME 8 1 1 5 2 8 GAME 9 0 4 1 5 8 GAME 10 2 1 0 1 8 GAME 11 3 2 3 0 8 GAME 12 2 0 3 5 8 GAME 13 0 3 1 1 8 GAME 14 1 0 4 3 8 GAME 15 1 1 3 1 8 GAME 16 2 2 0 1 8 GAME 17 2 1 3 1 5 8 G...
output:
RNKBRQBN RKBNQBRN QNNBBRKR BRNBNQKR QRNBKNBR RNKBRQBN RKBNQBRN QNNBBRKR BRKBNNQR NRQBNKBR NRQBKNBR RNKBRQBN RNBBQKNR RNKNBRQB NRNBKQBR RNKBRQBN RQBNNBKR NNQRBBKR RKNNBBRQ QRNNKBBR RNKBRQBN RQBNNBKR NNQRBBKR NBRNBQKR NRQNKBBR RNKBRQBN RQBNNBKR NRBBQKNR NBRQNKBR RBNQBKNR NRNQKBBR RNKBRQBN RQBNNBKR BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 149ms
memory: 3868kb
input:
GAME 1 0 3 1 6 8 GAME 2 1 2 4 3 8 GAME 3 0 3 1 8 GAME 4 1 1 1 1 2 8 GAME 5 1 1 1 0 8 GAME 6 2 0 2 1 8 GAME 7 1 3 4 1 8 GAME 8 0 1 8 GAME 9 1 3 5 8 GAME 10 2 1 3 4 5 8 GAME 11 1 3 4 2 4 8 GAME 12 2 1 2 4 8 GAME 13 2 4 2 2 4 8 GAME 14 2 6 4 8 GAME 15 1 4 1 4 8 GAME 16 2 4 1 8 GAME 17 2 3 5 8 GAME 18 1...
output:
RNKBRQBN BBRNQNKR BRNQNBKR NBBRKNQR QBBRKNNR RNKBRQBN RQBNNBKR NRBBQKNR NRBKRBNQ NBBRKQNR RNKBRQBN BBRNQNKR BRNQNBKR NBBRKNQR RNKBRQBN RQBNNBKR BBRNQKRN QRKNBRNB NRBBKNRQ QBNRKNBR RNKBRQBN RQBNNBKR BBRNQKRN QRKNBRNB NBQRKNBR RNKBRQBN RKBNQBRN QNNBBRKR BRKBNNQR NBNRKQBR RNKBRQBN RQBNNBKR NNQRBBKR NBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 135ms
memory: 3936kb
input:
GAME 1 0 4 2 4 8 GAME 2 0 6 8 GAME 3 0 5 3 8 GAME 4 1 3 1 4 2 8 GAME 5 2 1 2 0 1 8 GAME 6 2 0 3 6 8 GAME 7 0 4 3 2 4 8 GAME 8 0 3 2 8 GAME 9 0 4 4 5 8 GAME 10 1 3 1 2 2 8 GAME 11 1 2 3 8 GAME 12 1 2 4 1 2 8 GAME 13 2 0 5 3 3 8 GAME 14 1 2 5 3 4 8 GAME 15 2 0 4 2 8 GAME 16 3 4 1 2 8 GAME 17 2 0 2 3 8...
output:
RNKBRQBN BBRNQNKR NBQRBNKR BBRKNNRQ BBRQNKNR RNKBRQBN BBRNQNKR BBRNQKNR RNKBRQBN BBRNQNKR NBBNQRKR BBRNNKQR RNKBRQBN RQBNNBKR NNQRBBKR BQRKNBRN BRKNNBRQ BQRBNKNR RNKBRQBN RKBNQBRN RBNQNKBR NRKRNBBQ RNNKBRQB BNRBQKNR RNKBRQBN RKBNQBRN QNNBBRKR BNRBKNQR BNRBNKQR RNKBRQBN BBRNQNKR NBQRBNKR BRQNNBKR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 135ms
memory: 3644kb
input:
GAME 1 2 1 3 3 8 GAME 2 3 4 2 8 GAME 3 4 1 3 8 GAME 4 1 6 4 8 GAME 5 2 3 0 8 GAME 6 2 2 3 2 6 8 GAME 7 1 3 3 3 5 8 GAME 8 1 2 4 1 5 8 GAME 9 2 0 4 8 GAME 10 0 4 3 8 GAME 11 0 3 8 GAME 12 0 5 4 2 8 GAME 13 1 4 3 3 8 GAME 14 1 3 3 3 8 GAME 15 2 1 2 3 0 8 GAME 16 0 3 5 3 8 GAME 17 0 2 2 5 8 GAME 18 0 4...
output:
RNKBRQBN RKBNQBRN RBNQNKBR BNNQRBKR RQNBBNKR RNKBRQBN RNBBQKNR RNBKQBRN RNQBBNKR RNKBRQBN RBKNQRBN NNQBRKBR RNNBBQKR RNKBRQBN RQBNNBKR RQBKNBNR RQNNBBKR RNKBRQBN RKBNQBRN NBBQRKRN RNQNBBKR RNKBRQBN RKBNQBRN RKQBBNNR RBKNBRNQ RNNKBBQR RNNQBBKR RNKBRQBN RQBNNBKR NNQRBBKR RBNQBNKR NRBBQNKR BRQBNNKR RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed