QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178158 | #7179. Fischer's Chess Guessing Game | ucup-team859 | AC ✓ | 42ms | 5756kb | C++14 | 2.2kb | 2023-09-13 18:42:57 | 2023-09-13 18:42:58 |
Judging History
answer
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>
#include <map>
using namespace std;
vector<string> a;
int hamming(const string &a, const string &b) {
int nr = 0;
for (int i = 0; i < a.size(); ++i)
if (a[i] == b[i])
++nr;
return nr;
}
map<pair<vector<string>, int>, pair<string, int>> f;
int get_depth(const vector<string> &pos, int depth = 6) {
//cout << depth << endl;
if (depth < 0)
return 1;
if (pos.size() == 0)
return 0;
if (pos.size() == 1) {
f[{pos, depth}] = {pos[0], 1};
return 1;
}
if (pos.size() == 2) {
f[{pos, depth}] = {pos[0], 2};
return 2;
}
if (f.count({pos, depth}))
return f[{pos, depth}].second;
int best = depth + 1;
string wh;
for (auto it : pos) {
vector<string> cnt[9];
for (auto it2 : pos)
cnt[hamming(it, it2)].push_back(it2);
int mx = 0;
for (int i = 0; i <= 8 && mx < best; ++i)
mx = max(mx, 1 + get_depth(cnt[i], depth - 1));
if (mx < best) {
best = mx;
wh = it;
}
if (best <= depth)
break;
}
for (int j = 0; j <= depth; ++j)
f[{pos, j}] = {wh, best};
return best;
}
void solve() {
vector<string> pos = a;
int nr = 6, depth = 6;
bool first = true;
while (!pos.empty() && nr--) {
(void)get_depth(pos, depth);
string wh = f[{pos, depth}].first;
depth -= 1;
vector<string> bst[9];
for (auto it : pos)
bst[hamming(it, wh)].push_back(it);
//for (int i = 0; i <= 8; ++i)
// cout << bst[i].size() << " ";
//cout << endl;
int x;
cout << wh << endl;
cin >> x;
if (x == 8)
break;
pos = bst[x];
}
if (nr == -1)
exit(0);
}
int main() {
string s = "RQKBBNRN";
sort(s.begin(), s.end());
do {
int sum = 0, nr = 0, bad = false;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'B')
sum += i & 1;
else if (s[i] == 'R')
nr += 1;
else if (s[i] == 'K' && nr != 1) {
bad = true;
break;
}
}
if (sum != 1 || bad)
continue;
a.push_back(s);
} while(next_permutation(s.begin(), s.end()));
while (1) {
cin >> s;
if (s == "END")
break;
int x;
cin >> x;
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 5688kb
input:
GAME 1 0 1 2 2 8 END
output:
BBNNQRKR NNBBRKRQ NRKRBBQN RKBRNNQB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 38ms
memory: 5652kb
input:
GAME 1 0 1 2 2 8 GAME 2 0 1 3 8 GAME 3 0 2 2 1 2 8 GAME 4 1 2 1 2 3 8 GAME 5 0 1 1 4 8 GAME 6 0 2 1 2 8 GAME 7 0 0 4 0 8 GAME 8 1 1 1 3 0 8 GAME 9 1 0 2 1 4 8 GAME 10 0 0 2 8 GAME 11 1 0 1 1 4 8 GAME 12 1 0 0 8 GAME 13 0 0 2 4 8 GAME 14 2 1 2 2 1 8 GAME 15 1 0 1 2 8 GAME 16 0 0 0 8 GAME 17 2 1 1 1 5...
output:
BBNNQRKR NNBBRKRQ NRKRBBQN RKBRNNQB RKRBBQNN BBNNQRKR NNBBRKRQ NRKRBBQN RKRBBNQN BBNNQRKR NNBBRKRQ NQRKBBRN NRKRNBBQ QNRKRNBB RKRBBNNQ BBNNQRKR BNQBRKRN NBBRKQRN NQRBBKNR RNKBNQBR RKRBQNBN BBNNQRKR NNBBRKRQ NRKRBBQN RKBRNQNB RKRBNQBN BBNNQRKR NNBBRKRQ NQRKBBRN NRKQRNBB RKRBNNBQ BBNNQRKR NNBBRKRQ QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 42ms
memory: 5756kb
input:
GAME 1 1 2 0 2 4 8 GAME 2 2 0 3 1 8 GAME 3 2 1 2 8 GAME 4 1 2 0 1 5 8 GAME 5 3 1 1 0 8 GAME 6 2 0 3 2 3 8 GAME 7 2 1 2 4 2 8 GAME 8 2 0 1 1 6 8 GAME 9 3 1 2 2 3 8 GAME 10 2 1 3 2 3 8 GAME 11 2 0 1 0 8 GAME 12 4 2 1 2 4 8 GAME 13 1 1 2 3 1 8 GAME 14 1 1 4 4 3 8 GAME 15 1 0 2 0 8 GAME 16 2 4 2 1 8 GAM...
output:
BBNNQRKR BNQBRKRN NBBRKQRN BQRKRNNB RKNBRNBQ RKQBBNNR BBNNQRKR BBQRKNRN NNBBRQKR NNRKQBBR RKNBBQNR BBNNQRKR BBQRKNRN BNRKNBQR RKNBBNQR BBNNQRKR BNQBRKRN NBBRKQRN BQRKRNNB RNQKNBBR RKQBNNBR BBNNQRKR BBNQRKRN BNQRNBKR BQRNKRNB RKNBQNBR BBNNQRKR BBQRKNRN NNBBRQKR NNRKQBBR NRNBBKQR RKNBNQBR BBNNQRKR BBQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 39ms
memory: 5720kb
input:
GAME 1 0 0 8 GAME 2 0 1 8 GAME 3 0 2 3 4 4 8 GAME 4 0 0 6 8 GAME 5 0 1 5 8 GAME 6 0 1 6 8 GAME 7 0 0 6 4 8 GAME 8 1 1 3 3 0 8 GAME 9 0 2 2 8 GAME 10 0 0 4 8 GAME 11 1 0 2 3 8 GAME 12 0 1 4 8 GAME 13 1 4 1 8 GAME 14 1 4 2 4 8 GAME 15 1 3 2 5 8 GAME 16 1 3 2 4 8 GAME 17 2 2 2 4 4 8 GAME 18 2 1 2 0 8 G...
output:
BBNNQRKR NNBBRKRQ QRKRBBNN BBNNQRKR NNBBRKRQ NRKRBBQN BBNNQRKR NNBBRKRQ NQRKBBRN NRKQBNRB NRKQRBBN NRKRBBNQ BBNNQRKR NNBBRKRQ QRKRBBNN QRKRBNNB BBNNQRKR NNBBRKRQ NRKRBBQN NRKRBQNB BBNNQRKR NNBBRKRQ NRKRBBQN NRKRBNQB BBNNQRKR NNBBRKRQ QRKRBBNN QRKRBNNB QRKRNBBN BBNNQRKR BNQBRKRN BRKRNNQB NRBKQNRB RNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 38ms
memory: 5680kb
input:
GAME 1 1 2 1 1 1 8 GAME 2 0 2 3 0 8 GAME 3 1 2 0 2 5 8 GAME 4 1 1 2 0 4 8 GAME 5 0 2 1 4 4 8 GAME 6 1 2 1 0 4 8 GAME 7 3 2 2 0 5 8 GAME 8 2 2 0 3 5 8 GAME 9 2 1 2 1 5 8 GAME 10 2 3 3 0 8 GAME 11 3 3 3 1 3 8 GAME 12 3 2 2 0 3 8 GAME 13 2 3 2 1 4 8 GAME 14 4 2 1 2 8 GAME 15 3 2 1 4 8 GAME 16 1 0 3 5 8...
output:
BBNNQRKR BNQBRKRN NBBRKQRN NQRBBKNR RKQNBNRB RQNKRBBN BBNNQRKR NNBBRKRQ NQRKBBRN NRKQBNRB RNQKRBBN BBNNQRKR BNQBRKRN NBBRKQRN BQRKRNNB RKNBRNBQ RNNKRBBQ BBNNQRKR BNQBRKRN BRKRNNQB NRKBBRNQ RQBNKNRB RQNKRNBB BBNNQRKR NNBBRKRQ NQRKBBRN NRKQRNBB QRBKRNNB RNQKRNBB BBNNQRKR BNQBRKRN NBBRKQRN NQRBBKNR QRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 40ms
memory: 5680kb
input:
GAME 1 0 2 4 1 8 GAME 2 1 2 4 3 8 GAME 3 0 4 3 5 8 GAME 4 0 2 2 2 8 GAME 5 1 1 3 8 GAME 6 0 3 5 8 GAME 7 1 2 2 2 8 GAME 8 0 2 6 4 8 GAME 9 1 1 1 0 5 8 GAME 10 1 1 3 5 5 8 GAME 11 0 2 4 4 8 GAME 12 1 1 2 3 4 8 GAME 13 2 2 1 8 GAME 14 4 2 2 4 8 GAME 15 3 2 2 4 8 GAME 16 1 0 4 4 8 GAME 17 2 0 3 5 8 GAM...
output:
BBNNQRKR NNBBRKRQ NQRKBBRN NQRKRNBB QRBKNBRN BBNNQRKR BNQBRKRN NBBRKQRN NBRKRQBN NRBKQBRN BBNNQRKR NNBBRKRQ NNBRKQRB NNRKBBRQ NRBKNBRQ BBNNQRKR NNBBRKRQ NQRKBBRN NRKRNBBQ QRBKNNRB BBNNQRKR BNQBRKRN BRKRNNQB NRBKQNRB BBNNQRKR NNBBRKRQ NNRKBQRB NRBKNQRB BBNNQRKR BNQBRKRN NBBRKQRN NQRNBKRB QRNKBBRN BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 40ms
memory: 5684kb
input:
GAME 1 2 3 2 0 4 8 GAME 2 3 2 2 0 8 GAME 3 3 1 0 5 8 GAME 4 3 2 3 2 1 8 GAME 5 3 4 3 5 8 GAME 6 4 4 5 8 GAME 7 1 2 3 1 6 8 GAME 8 1 3 1 1 3 8 GAME 9 1 2 2 0 0 8 GAME 10 2 1 0 3 1 8 GAME 11 1 1 1 4 2 8 GAME 12 2 1 2 2 0 8 GAME 13 2 2 2 1 3 8 GAME 14 1 4 3 2 8 GAME 15 2 1 1 4 8 GAME 16 3 1 0 4 6 8 GAM...
output:
BBNNQRKR BBQRKNRN BBRKRNNQ BNQNRKRB NBBRKQNR RBBQKRNN BBNNQRKR BBNQRKRN BBQRKNNR BNRQNBKR RBBNKRQN BBNNQRKR BBNQRKRN BNQRNBKR NBRNKRBQ RBBNKRNQ BBNNQRKR BBNQRKRN BBQRKNNR BBRKNRNQ NBRQBNKR RBQNKRBN BBNNQRKR BBNQRKRN BBNRKNRQ BBRQKRNN RBNQKRBN BBNNQRKR BBNNRKRQ BBNRKRNQ RBNNKRBQ BBNNQRKR BNQBRKRN NBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 41ms
memory: 5676kb
input:
GAME 1 2 2 2 4 1 8 GAME 2 1 2 2 1 8 GAME 3 2 1 1 8 GAME 4 3 1 2 2 4 8 GAME 5 2 2 0 2 8 GAME 6 2 1 2 2 3 8 GAME 7 3 4 3 8 GAME 8 4 3 4 5 8 GAME 9 4 4 6 8 GAME 10 2 3 3 4 3 8 GAME 11 2 3 2 2 0 8 GAME 12 2 2 4 8 GAME 13 3 1 1 8 GAME 14 2 2 2 1 2 8 GAME 15 3 1 2 8 GAME 16 3 2 2 1 2 8 GAME 17 2 3 2 0 3 8...
output:
BBNNQRKR BBQRKNRN BNNBRKRQ BRKBNNQR BRKNNQRB QRNBKNBR BBNNQRKR BNQBRKRN NBBRKQRN NQRNBKRB NRQBKNBR BBNNQRKR BBQRKNRN BNRKNBQR NRNBKQBR BBNNQRKR BBNQRKRN BNQRNBKR BNRNKRQB RBQNKNBR QRNNKBBR BBNNQRKR BBQRKNRN BNNBRKRQ NBRKBNQR NRQNKBBR BBNNQRKR BBQRKNRN BNRKNBQR RKNBBNQR NBRQBKNR NRNQKBBR BBNNQRKR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 41ms
memory: 5704kb
input:
GAME 1 2 4 2 2 4 8 GAME 2 2 3 2 0 8 GAME 3 2 4 2 2 3 8 GAME 4 3 2 5 4 8 GAME 5 2 5 2 8 GAME 6 3 2 4 3 8 GAME 7 1 1 1 2 3 8 GAME 8 1 0 8 GAME 9 1 1 2 1 0 8 GAME 10 2 2 2 1 8 GAME 11 2 2 1 2 3 8 GAME 12 1 2 3 8 GAME 13 1 3 2 0 6 8 GAME 14 3 4 2 2 8 GAME 15 2 2 3 0 8 GAME 16 2 4 2 1 3 8 GAME 17 2 3 1 3...
output:
BBNNQRKR BBQRKNRN BBRKNNRQ BNNRKQRB BRQBKNNR QBBRKNNR BBNNQRKR BBQRKNRN BBRKRNNQ BNQNRKRB NBBRKQNR BBNNQRKR BBQRKNRN BBRKNNRQ BNNRKQRB BRQBKNNR NBBRKNQR BBNNQRKR BBNQRKRN BBQRKNNR BQNRKBNR QBNRKNBR BBNNQRKR BBQRKNRN BQNRKBRN NBQRKNBR BBNNQRKR BBNQRKRN BBQRKNNR BBRKNQNR NBNRKQBR BBNNQRKR BNQBRKRN BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 33ms
memory: 5668kb
input:
GAME 1 3 4 2 8 GAME 2 5 5 3 8 GAME 3 4 4 2 8 GAME 4 2 1 4 8 GAME 5 3 2 3 3 8 GAME 6 2 1 6 8 GAME 7 3 2 3 3 4 8 GAME 8 2 1 2 2 8 GAME 9 3 2 2 2 8 GAME 10 3 2 2 3 8 GAME 11 2 1 3 2 2 8 GAME 12 4 3 2 2 8 GAME 13 1 3 2 1 2 8 GAME 14 1 2 1 8 GAME 15 1 3 2 0 1 8 GAME 16 1 3 3 8 GAME 17 1 2 1 6 8 GAME 18 2...
output:
BBNNQRKR BBNQRKRN BBNRKNRQ BBRQNKNR BBNNQRKR BBNNRKQR BBNQRNKR BBRNQKNR BBNNQRKR BBNNRKRQ BBNRKRNQ BBRNNKQR BBNNQRKR BBQRKNRN BNRKNBQR BQRBNKNR BBNNQRKR BBNQRKRN BBQRKNNR BBRKNRNQ BNRBQKNR BBNNQRKR BBQRKNRN BNRKNBQR BNRBNKQR BBNNQRKR BBNQRKRN BBQRKNNR BBRKNRNQ BNRBQKNR QBRNBKNR BBNNQRKR BBQRKNRN BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 36ms
memory: 5644kb
input:
GAME 1 3 1 2 0 5 8 GAME 2 2 2 2 3 8 GAME 3 3 1 3 1 8 GAME 4 4 2 2 0 6 8 GAME 5 3 0 4 5 2 8 GAME 6 3 2 1 1 4 8 GAME 7 3 1 5 5 8 GAME 8 5 3 5 8 GAME 9 4 2 4 4 8 GAME 10 4 2 5 5 8 GAME 11 4 2 4 5 8 GAME 12 6 5 4 5 8 GAME 13 2 1 2 3 6 8 GAME 14 3 0 5 8 GAME 15 2 0 6 4 8 GAME 16 3 0 4 2 4 8 GAME 17 2 0 4...
output:
BBNNQRKR BBNQRKRN BNQRNBKR BNRNKRQB NRNBBQKR RQNBBNKR BBNNQRKR BBQRKNRN BNNBRKRQ BRKBNNQR RNQBBNKR BBNNQRKR BBNQRKRN BNQRNBKR BQRNKBNR RNNBBQKR BBNNQRKR BBNNRKRQ BBQRNNKR BBRKQRNN QRNNBBKR RQNNBBKR BBNNQRKR BBNQRKRN NNBRQBKR NNQBBRKR NQBBNRKR RNQNBBKR BBNNQRKR BBNQRKRN BBQRKNNR BRNKNRQB RNNBQKBR RNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed