QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178443 | #7179. Fischer's Chess Guessing Game | Andycipation | AC ✓ | 22ms | 7604kb | C++17 | 2.5kb | 2023-09-13 23:54:42 | 2023-09-13 23:54:43 |
Judging History
answer
/*
* author: ADMathNoob
* created: 09/13/23 10:42:01
* problem: https://qoj.ac/problem/7179
*/
/*
Comments about problem:
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 960;
const int V = 3 * N;
int nodes = 0;
int sz[V];
int ask[V];
int child[V][8];
int res[N][N];
void Dfs(int x, const vector<int>& v) {
// debug(x, v);
sz[x] = v.size();
if (sz[x] == 1) {
ask[x] = v[0];
return;
}
int best = v.size();
for (int a = 0; a < N; a++) {
vector<int> cnt(8);
for (int i : v) {
if (i != a) {
cnt[res[a][i]] += 1;
}
}
int mx = *max_element(cnt.begin(), cnt.end());
if (mx < best) {
best = mx;
ask[x] = a;
}
}
vector<vector<int>> split(8);
for (int i : v) {
if (i != ask[x]) {
split[res[ask[x]][i]].push_back(i);
}
}
for (int r = 0; r < 8; r++) {
if (!split[r].empty()) {
int c = nodes++;
child[x][r] = c;
Dfs(c, split[r]);
} else {
child[x][r] = -1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<string> all;
for (int b0 = 0; b0 < 8; b0 += 2) {
for (int b1 = 1; b1 < 8; b1 += 2) {
for (int r0 = 0; r0 < 8; r0++) {
for (int k = r0 + 1; k < 8; k++) {
for (int r1 = k + 1; r1 < 8; r1++) {
for (int q = 0; q < 8; q++) {
set<int> p = {b0, b1, r0, k, r1, q};
if (p.size() == 6) {
string s(8, 'N');
s[b0] = s[b1] = 'B';
s[r0] = s[r1] = 'R';
s[k] = 'K';
s[q] = 'Q';
all.push_back(s);
}
}
}
}
}
}
}
assert(all.size() == N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int d = 0;
for (int t = 0; t < 8; t++) {
d += (all[i][t] == all[j][t]);
}
res[i][j] = d;
}
}
vector<int> nums(N);
iota(nums.begin(), nums.end(), 0);
Dfs(nodes++, nums);
while (true) {
{
string s;
cin >> s;
if (s == "END") {
break;
}
assert(s == "GAME");
cin >> s;
}
int v = 0;
while (true) {
cout << all[ask[v]] << endl;
int r;
cin >> r;
if (r == 8) {
break;
}
v = child[v][r];
assert(v != -1);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 14ms
memory: 7304kb
input:
GAME 1 1 0 3 5 8 END
output:
NRBBNKQR BRNNKBQR NQRKBRNB RKBBQRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 18ms
memory: 7552kb
input:
GAME 1 1 0 3 5 8 GAME 2 2 3 3 1 2 8 GAME 3 1 0 3 4 2 8 GAME 4 1 0 1 2 3 8 GAME 5 2 3 4 2 8 GAME 6 2 2 5 2 8 GAME 7 0 2 3 4 8 GAME 8 1 3 3 1 2 8 GAME 9 0 3 3 3 8 GAME 10 0 3 3 2 8 GAME 11 0 5 3 3 8 GAME 12 1 2 2 0 1 8 GAME 13 1 1 5 3 8 GAME 14 0 4 2 4 8 GAME 15 1 2 1 2 1 8 GAME 16 1 0 2 1 1 8 GAME 17...
output:
NRBBNKQR BRNNKBQR NQRKBRNB RKBBQRNN RKRBBQNN NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBRKRQNN RKRBBNQN NRBBNKQR BRNNKBQR NQRKBRNB RKBBQRNN BBRKRQNN RKRBBNNQ NRBBNKQR BRNNKBQR NQRKBRNB RNKBBQNR BBRKRNQN RKRBQNBN NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RKRBNQBN NRBBNKQR RNBBQKRN RKBBRNNQ BBRKRNQN RKRBNNBQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 18ms
memory: 7340kb
input:
GAME 1 2 2 5 1 8 GAME 2 2 2 4 0 2 8 GAME 3 3 1 3 1 0 8 GAME 4 3 1 2 2 1 8 GAME 5 2 3 5 2 8 GAME 6 3 1 1 3 0 8 GAME 7 1 3 5 0 8 GAME 8 1 3 3 2 1 8 GAME 9 2 1 3 2 0 8 GAME 10 2 1 0 0 1 8 GAME 11 2 1 1 3 0 8 GAME 12 1 4 3 2 8 GAME 13 0 2 2 6 8 GAME 14 1 1 2 3 4 8 GAME 15 0 1 0 2 8 GAME 16 0 2 2 5 8 GAM...
output:
NRBBNKQR RNBBQKRN RKBBRNNQ BBRKRNQN RKQBBNNR NRBBNKQR RNBBQKRN RKBBRNNQ BBRKNRQN BBRKRQNN RKNBBQNR NRBBNKQR RBBNQKRN BRKBRNQN BBRKNQNR BBRKRQNN RKNBBNQR NRBBNKQR RBBNQKRN BRKBRNQN BBRNKNQR BBRKRNQN RKQBNNBR NRBBNKQR RNBBQKRN RQKBNNBR BBRKQNRN RKNBQNBR NRBBNKQR RBBNQKRN BRKBRNQN BNNBRKQR BBRKRNQN RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 22ms
memory: 7604kb
input:
GAME 1 1 2 1 4 1 8 GAME 2 3 1 4 1 8 GAME 3 2 0 3 1 1 8 GAME 4 1 1 0 2 8 GAME 5 2 0 4 0 0 8 GAME 6 3 0 1 2 0 8 GAME 7 2 1 1 0 8 GAME 8 2 2 0 0 1 8 GAME 9 3 0 0 6 8 GAME 10 2 0 4 1 0 8 GAME 11 2 1 3 1 0 8 GAME 12 3 0 0 4 8 GAME 13 2 2 3 4 5 8 GAME 14 3 1 8 GAME 15 2 1 1 3 3 8 GAME 16 1 3 0 4 8 GAME 17...
output:
NRBBNKQR BRNNKBQR BNRBKRQN BRKQNBNR BBRKRNQN QRKRBBNN NRBBNKQR RBBNQKRN BRKBRNQN QNRBBNKR NRKRBBQN NRBBNKQR RNBBQKRN BRKQNRNB BBRKNQNR BBRKRQNN NRKRBBNQ NRBBNKQR BRNNKBQR RKQNRBBN BBRKRNNQ QRKRBNNB NRBBNKQR RNBBQKRN BRKQNRNB BBNQRNKR BBRKRNQN NRKRBQNB NRBBNKQR RBBNQKRN BNRBQNKR BBRKNNQR BBRKRQNN NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 15ms
memory: 7372kb
input:
GAME 1 0 4 1 1 8 GAME 2 0 3 0 3 8 GAME 3 0 4 2 3 8 GAME 4 0 5 0 2 8 GAME 5 0 4 2 2 8 GAME 6 0 6 0 3 8 GAME 7 1 0 3 6 4 8 GAME 8 3 4 3 3 8 GAME 9 2 2 4 4 8 GAME 10 0 1 1 4 8 GAME 11 1 2 3 2 3 8 GAME 12 0 2 4 0 8 GAME 13 1 0 2 5 3 8 GAME 14 0 3 1 1 8 GAME 15 1 1 2 1 2 8 GAME 16 2 2 3 1 2 8 GAME 17 1 0...
output:
NRBBNKQR RKNNRQBB RBKNBNRQ BNNBQRKR RQNKRBBN NRBBNKQR RKNNRQBB BQRNKRNB RBKNRNBQ RNQKRBBN NRBBNKQR RKNNRQBB RBKNBNRQ BNRKQBRN RNNKRBBQ NRBBNKQR RKNNRQBB BBRNKQRN BBRKRQNN RQNKRNBB NRBBNKQR RKNNRQBB RBKNBNRQ BNRKQBRN RNQKRNBB NRBBNKQR RKNNRQBB BRKNNBRQ BBRKRQNN RNNKRQBB NRBBNKQR BRNNKBQR NQRKBRNB RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 12ms
memory: 7384kb
input:
GAME 1 3 3 1 4 8 GAME 2 3 4 0 8 GAME 3 4 1 0 1 8 GAME 4 3 2 0 4 8 GAME 5 3 3 0 0 1 8 GAME 6 4 1 0 2 8 GAME 7 1 3 1 1 2 8 GAME 8 2 2 0 1 2 8 GAME 9 2 1 5 1 8 GAME 10 1 2 0 0 1 8 GAME 11 2 1 5 2 8 GAME 12 2 1 6 1 8 GAME 13 3 0 2 3 3 8 GAME 14 2 1 3 5 3 8 GAME 15 4 4 3 2 8 GAME 16 4 3 1 1 8 GAME 17 4 4...
output:
NRBBNKQR RBBNQKRN BBQRNKNR BBRKNQRN QRBKNBRN NRBBNKQR RBBNQKRN BBRNNKQR NRBKQBRN NRBBNKQR BRNBQKNR BBRNKNQR BBRKRQNN NRBKNBRQ NRBBNKQR RBBNQKRN BBQNRKNR RNBKNBRQ QRBKNNRB NRBBNKQR RBBNQKRN BBQRNKNR BBRNKRNQ BBRKRQNN NRBKQNRB NRBBNKQR BRNBQKNR BBRNKNQR BBRKRQNN NRBKNQRB NRBBNKQR BRNNKBQR RBQNBNKR BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 17ms
memory: 7568kb
input:
GAME 1 1 1 2 4 4 8 GAME 2 2 3 1 2 2 8 GAME 3 1 2 2 2 1 8 GAME 4 0 3 3 5 8 GAME 5 0 3 2 2 8 GAME 6 0 4 4 1 8 GAME 7 2 4 2 2 8 GAME 8 3 3 0 2 2 8 GAME 9 2 4 3 0 8 GAME 10 1 2 2 1 8 GAME 11 1 1 1 8 GAME 12 2 3 1 0 8 GAME 13 1 2 4 1 8 GAME 14 1 1 4 1 1 8 GAME 15 1 2 4 0 8 GAME 16 0 5 2 0 8 GAME 17 0 4 2...
output:
NRBBNKQR BRNNKBQR RKQNRBBN BBRQKNRN BBRKQRNN RBBQKRNN NRBBNKQR RNBBQKRN RQKBNNBR BBRKNQRN BBRKRQNN RBBNKRQN NRBBNKQR BRNNKBQR BNRBKRQN BBNRKQRN BBRKRNQN RBBNKRNQ NRBBNKQR RKNNRQBB BQRNKRNB RBKNBRQN RBQNKRBN NRBBNKQR RKNNRQBB BQRNKRNB RKNRBBNQ RBNQKRBN NRBBNKQR RKNNRQBB RBKNBNRQ BBRKQNRN RBNNKRBQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 12ms
memory: 7348kb
input:
GAME 1 3 0 3 3 8 GAME 2 4 3 1 4 8 GAME 3 4 4 1 4 8 GAME 4 2 0 1 2 0 8 GAME 5 3 1 1 1 1 8 GAME 6 3 0 1 1 0 8 GAME 7 0 0 6 5 8 GAME 8 1 4 1 5 8 GAME 9 0 1 5 4 8 GAME 10 1 2 6 3 8 GAME 11 2 3 1 3 3 8 GAME 12 1 2 6 4 8 GAME 13 0 2 0 2 8 GAME 14 0 1 6 8 GAME 15 1 4 2 3 8 GAME 16 0 2 0 3 8 GAME 17 1 1 2 5...
output:
NRBBNKQR RBBNQKRN BNRBQNKR BRKBRNNQ QRNBKNBR NRBBNKQR BRNBQKNR BBQRNKRN BNQBRNKR NRQBKNBR NRBBNKQR BRNBQKNR BQNRNKRB BBNRKQNR NRNBKQBR NRBBNKQR RNBBQKRN BRKQNRNB BBRQKNNR BBRKRQNN QRNNKBBR NRBBNKQR RBBNQKRN BRKBRNQN BNNBRKQR BBRQKRNN NRQNKBBR NRBBNKQR RBBNQKRN BNRBQNKR BBRKNNQR BBRKRQNN NRNQKBBR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 16ms
memory: 7536kb
input:
GAME 1 2 1 0 3 2 8 GAME 2 3 2 3 5 8 GAME 3 4 1 5 8 GAME 4 1 3 3 3 1 8 GAME 5 2 0 0 1 1 8 GAME 6 2 0 0 1 2 8 GAME 7 2 2 2 2 0 8 GAME 8 3 1 0 1 8 GAME 9 4 1 3 1 8 GAME 10 1 4 4 1 8 GAME 11 2 0 0 3 0 8 GAME 12 2 1 1 1 0 8 GAME 13 3 6 1 2 8 GAME 14 2 6 2 2 8 GAME 15 3 6 2 1 8 GAME 16 1 1 4 1 2 8 GAME 17...
output:
NRBBNKQR RNBBQKRN NRNKBRQB BBRKRNNQ BBRKRNQN QBBRKNNR NRBBNKQR RBBNQKRN BBQNRKNR NBBRQNKR NBBRKQNR NRBBNKQR BRNBQKNR BBRNKNQR NBBRKNQR NRBBNKQR BRNNKBQR RBQNBNKR BBRKQNNR BBRKRQNN QBNRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNKBRN BBRKRQNN NBQRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNKBRN BBRKRQNN NBNRKQBR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 21ms
memory: 7336kb
input:
GAME 1 3 2 5 4 8 GAME 2 2 2 1 4 4 8 GAME 3 4 3 4 3 8 GAME 4 4 5 4 2 8 GAME 5 3 2 4 3 8 GAME 6 5 5 2 8 GAME 7 2 1 1 4 3 8 GAME 8 3 2 4 2 8 GAME 9 4 2 1 3 8 GAME 10 3 3 4 3 2 8 GAME 11 4 2 1 2 8 GAME 12 3 4 5 3 8 GAME 13 3 1 1 4 8 GAME 14 4 4 2 2 8 GAME 15 5 3 2 1 8 GAME 16 4 3 2 3 8 GAME 17 5 5 3 8 G...
output:
NRBBNKQR RBBNQKRN BBQNRKNR BBRKRQNN BBRQNKNR NRBBNKQR RNBBQKRN RKBBRNNQ BBRKQNRN BBRKRQNN BBRNQKNR NRBBNKQR BRNBQKNR BBQRNKRN BBRKRQNN BBRNNKQR NRBBNKQR BRNBQKNR BBRNKQNR BBRKRNQN BQRBNKNR NRBBNKQR RBBNQKRN BBQNRKNR BBRKQNRN BNRBQKNR NRBBNKQR BQRBNNKR NRBBQNKR BNRBNKQR NRBBNKQR RNBBQKRN NRNKBRQB BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 22ms
memory: 7604kb
input:
GAME 1 2 2 3 2 0 8 GAME 2 2 3 4 4 8 GAME 3 2 3 3 3 0 8 GAME 4 1 4 4 3 8 GAME 5 1 3 6 0 8 GAME 6 1 3 4 0 8 GAME 7 4 4 2 1 8 GAME 8 3 1 4 4 8 GAME 9 4 5 3 2 8 GAME 10 3 1 2 3 8 GAME 11 3 0 3 2 8 GAME 12 2 1 2 3 8 GAME 13 5 5 6 8 GAME 14 5 4 0 8 GAME 15 6 1 1 8 GAME 16 4 2 2 0 8 GAME 17 5 3 3 0 8 GAME ...
output:
NRBBNKQR RNBBQKRN RKBBRNNQ BRKBNNRQ BBRQKRNN RQNBBNKR NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RNQBBNKR NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBRKRNQN RNNBBQKR NRBBNKQR BRNNKBQR QNBNRBKR BBRNQNKR RQNNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBRKRQNN RNQNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBRKRNNQ RNNQBBKR NRBBNKQR BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed