QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181910 | #7179. Fischer's Chess Guessing Game | USP_USP_USP# | AC ✓ | 119ms | 11396kb | C++20 | 2.5kb | 2023-09-17 03:47:10 | 2023-09-17 03:47:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define pb push_back
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const int N = 1e3;
int dist[N][N];
vector<string> tab;
void precalc () {
string s = "RRKQBBNN";
sort (all (s));
auto check = [&] (string t) {
vector<int> R;
for (int i = 0; i < 8; i++) if (s[i] == 'R') R.pb(i);
for (int i = 0; i < 8; i++) if (s[i] == 'K') {
if (i < R[0] || R[1] < i) return false;
}
int par = 0;
for (int i = 0; i < 8; i++) if (s[i] == 'B') if (i & 1) par++;
if (par != 1) return false;
return true;
};
do {
if (check (s)) tab.pb (s);
} while (next_permutation (all (s)));
// dbg (tab.size ());
for (int i = 0; i < tab.size (); i++) {
for (int j = 0; j < tab.size (); j++) {
for (int k = 0; k < 8; k++) dist[i][j] += (tab[i][k] == tab[j][k]);
}
}
}
void solve () {
vector<int> ativos;
for (int i = 0; i < 960; i++) ativos.pb (i);
auto find_best_tab = [&] () -> int {
vector<int> val (960, 1e12);
int best = 1e12;
for (int j = 0; j < 960; j++) {
vector<int> f(9);
for (auto u : ativos) f[dist[j][u]]++;
int mx = 0;
for (int i = 0; i <= 8; i++) mx = max (mx, f[i]);
val[j] = mx;
best = min (best, mx);
}
for (int j = 0; j < 960; j++) if (best == val[j]) return j;
assert (0);
return -1;
};
auto play = [&] (int j) -> bool {
cout << tab[j] << endl;
int filtro; cin >> filtro;
if (filtro == 8) return 1;
vector<int> add;
for (auto u : ativos) if (dist[j][u] == filtro) add.pb (u);
swap (add, ativos);
return 0;
};
while (true) {
int j = find_best_tab ();
if (play (j)) break;
if (ativos.size () == 1) {
cout << tab[ativos[0]] << endl;
int x; cin >> x;assert (x == 8);
break;
}
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
precalc ();
while (true) {
string op; cin >> op;
if (op == "END") exit (0);
int x; cin >> x;
solve ();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11132kb
input:
GAME 1 1 0 2 4 8 END
output:
NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 118ms
memory: 11392kb
input:
GAME 1 1 0 2 4 8 GAME 2 2 3 3 1 1 8 GAME 3 1 0 1 2 8 GAME 4 1 0 2 2 1 8 GAME 5 2 3 4 2 8 GAME 6 2 2 4 0 0 8 GAME 7 0 2 3 2 0 8 GAME 8 1 3 3 0 8 GAME 9 0 3 3 0 8 GAME 10 0 3 3 1 8 GAME 11 0 5 1 0 8 GAME 12 1 2 2 1 0 8 GAME 13 1 1 5 1 8 GAME 14 0 4 4 3 8 GAME 15 1 2 1 2 1 8 GAME 16 1 0 3 1 0 8 GAME 17...
output:
NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN RKRBBQNN NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBNNRKQR RKRBBNQN NRBBNKQR BRNNKBQR NBRKNQBR BNRKQRNB RKRBBNNQ NRBBNKQR BRNNKBQR NBRKNQBR QBRKBRNN BBNNQRKR RKRBQNBN NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RKRBNQBN NRBBNKQR RNBBQKRN QNRBKNBR BBNNQRKR BBNNRKQR RKRBNNBQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 119ms
memory: 11184kb
input:
GAME 1 2 2 3 1 2 8 GAME 2 2 2 2 5 2 8 GAME 3 3 1 4 2 8 GAME 4 3 1 3 1 1 8 GAME 5 2 3 5 2 8 GAME 6 3 1 3 0 2 8 GAME 7 1 3 5 1 8 GAME 8 1 3 3 4 8 GAME 9 2 1 3 2 3 8 GAME 10 2 1 0 0 4 8 GAME 11 2 1 1 3 2 8 GAME 12 1 4 3 4 8 GAME 13 0 2 2 3 8 GAME 14 1 1 2 2 2 8 GAME 15 0 1 0 1 8 GAME 16 0 2 2 1 8 GAME ...
output:
NRBBNKQR RNBBQKRN QNRBKNBR BNNQRBKR BBQNNRKR RKQBBNNR NRBBNKQR RNBBQKRN QNRBKNBR RBNNBQKR BBNNQRKR RKNBBQNR NRBBNKQR RBBNQKRN BQNBRNKR BRKRNNQB RKNBBNQR NRBBNKQR RBBNQKRN BQNBRNKR BBRNKNRQ BBNNRKQR RKQBNNBR NRBBNKQR RNBBQKRN RQKBNNBR BBNNRKQR RKNBQNBR NRBBNKQR RBBNQKRN BQNBRNKR BBRNKNRQ BBNQRKNR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 108ms
memory: 11056kb
input:
GAME 1 1 2 1 4 0 8 GAME 2 3 1 0 1 8 GAME 3 2 0 3 0 8 GAME 4 1 1 0 1 0 8 GAME 5 2 0 4 0 0 8 GAME 6 3 0 1 0 8 GAME 7 2 1 1 0 8 GAME 8 2 2 1 1 0 8 GAME 9 3 0 0 6 8 GAME 10 2 0 4 1 0 8 GAME 11 2 1 3 1 1 8 GAME 12 3 0 0 4 8 GAME 13 2 2 1 1 2 8 GAME 14 3 1 4 5 8 GAME 15 2 1 1 3 1 8 GAME 16 1 3 0 4 8 GAME ...
output:
NRBBNKQR BRNNKBQR BNRBKRQN BRKQNBNR BBNNQRKR QRKRBBNN NRBBNKQR RBBNQKRN BQNBRNKR BNQRKRNB NRKRBBQN NRBBNKQR RNBBQKRN BRKQNRNB BBQNNRKR NRKRBBNQ NRBBNKQR BRNNKBQR RKQNRBBN BBRKNNRQ BBNNQRKR QRKRBNNB NRBBNKQR RNBBQKRN BRKQNRNB BBNQRNKR BBNNQRKR NRKRBQNB NRBBNKQR RBBNQKRN BNRBQNKR BBNQNRKR NRKRBNQB NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 110ms
memory: 11188kb
input:
GAME 1 0 4 5 2 8 GAME 2 0 3 0 2 8 GAME 3 0 4 5 3 8 GAME 4 0 5 1 3 8 GAME 5 0 4 4 2 8 GAME 6 0 6 4 1 8 GAME 7 1 0 2 5 8 GAME 8 3 4 1 3 8 GAME 9 2 2 0 0 2 8 GAME 10 0 1 0 2 8 GAME 11 1 2 3 1 3 8 GAME 12 0 2 4 0 8 GAME 13 1 0 4 2 1 8 GAME 14 0 3 1 1 8 GAME 15 1 1 2 1 3 8 GAME 16 2 2 0 1 1 8 GAME 17 1 0...
output:
NRBBNKQR RKNNRQBB QNRKRBBN BBNNRKRQ RQNKRBBN NRBBNKQR RKNNRQBB BQRNKRNB NRKQRNBB RNQKRBBN NRBBNKQR RKNNRQBB QNRKRBBN BBNNRKRQ RNNKRBBQ NRBBNKQR RKNNRQBB BBNRKQRN BBNQRNKR RQNKRNBB NRBBNKQR RKNNRQBB QNRKRBBN BBRKQNRN RNQKRNBB NRBBNKQR RKNNRQBB BNNRKQRB BBNNQRKR RNNKRQBB NRBBNKQR BRNNKBQR NBRKNQBR QBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 114ms
memory: 11104kb
input:
GAME 1 3 3 1 2 0 8 GAME 2 3 4 0 0 8 GAME 3 4 3 1 0 8 GAME 4 3 2 0 3 8 GAME 5 3 3 0 2 1 8 GAME 6 4 2 0 1 8 GAME 7 1 3 1 1 1 8 GAME 8 2 2 0 4 0 8 GAME 9 2 1 5 1 8 GAME 10 1 2 0 2 1 8 GAME 11 2 1 5 0 8 GAME 12 2 1 6 2 8 GAME 13 3 0 2 3 2 8 GAME 14 2 1 3 5 4 8 GAME 15 4 2 4 4 8 GAME 16 4 1 4 5 8 GAME 17...
output:
NRBBNKQR RBBNQKRN BBQRNKNR BBNRQKRN BBNNRKQR QRBKNBRN NRBBNKQR RBBNQKRN BBNNRQKR BBNQRKNR NRBKQBRN NRBBNKQR BNRBNKRQ BNNRQBKR BNRBQKNR NRBKNBRQ NRBBNKQR RBBNQKRN BBNQRKNR BQRKNRNB QRBKNNRB NRBBNKQR RBBNQKRN BBQRNKNR BBRNKNRQ BBNNQRKR NRBKQNRB NRBBNKQR BNRBNKRQ BBNNRKQR BBNQRKRN NRBKNQRB NRBBNKQR BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 100ms
memory: 11348kb
input:
GAME 1 1 1 2 2 1 8 GAME 2 2 3 1 1 3 8 GAME 3 1 2 2 3 2 8 GAME 4 0 3 3 3 8 GAME 5 0 3 2 1 8 GAME 6 0 4 1 4 8 GAME 7 2 4 2 0 8 GAME 8 3 3 0 1 1 8 GAME 9 2 4 3 2 8 GAME 10 1 2 2 1 1 8 GAME 11 1 1 1 8 GAME 12 2 3 1 0 2 8 GAME 13 1 2 4 3 8 GAME 14 1 1 4 1 1 8 GAME 15 1 2 4 4 8 GAME 16 0 5 2 3 8 GAME 17 0...
output:
NRBBNKQR BRNNKBQR RKQNRBBN BBRNQKRN BBNNRKQR RBBQKRNN NRBBNKQR RNBBQKRN RQKBNNBR BBNRNKRQ BBNNQRKR RBBNKRQN NRBBNKQR BRNNKBQR BNRBKRQN BBNNRKRQ BBNQNRKR RBBNKRNQ NRBBNKQR RKNNRQBB BQRNKRNB NQNRKRBB RBQNKRBN NRBBNKQR RKNNRQBB BQRNKRNB QRNKBNRB RBNQKRBN NRBBNKQR RKNNRQBB QNRKRBBN BBNNQRKR RBNNKRBQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 112ms
memory: 11096kb
input:
GAME 1 3 0 3 3 8 GAME 2 4 1 2 2 8 GAME 3 4 1 2 4 8 GAME 4 2 0 1 2 3 8 GAME 5 3 1 1 2 2 8 GAME 6 3 0 1 3 3 8 GAME 7 0 0 6 3 8 GAME 8 1 4 1 5 8 GAME 9 0 1 4 4 8 GAME 10 1 2 6 2 8 GAME 11 2 3 1 1 2 8 GAME 12 1 2 6 1 8 GAME 13 0 2 0 3 8 GAME 14 0 1 5 2 8 GAME 15 1 4 2 3 8 GAME 16 0 2 0 2 8 GAME 17 1 1 2...
output:
NRBBNKQR RBBNQKRN BNRBQNKR BQNBNRKR QRNBKNBR NRBBNKQR BNRBNKRQ NQBRNBKR BBNRKQNR NRQBKNBR NRBBNKQR BNRBNKRQ NQBRNBKR BBNRKQNR NRNBKQBR NRBBNKQR RNBBQKRN BRKQNRNB BBRQKNNR BBNNQRKR QRNNKBBR NRBBNKQR RBBNQKRN BQNBRNKR BBRNNQKR BBNNQRKR NRQNKBBR NRBBNKQR RBBNQKRN BNRBQNKR BBNQNRKR BBNQRKNR NRNQKBBR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 100ms
memory: 11396kb
input:
GAME 1 2 1 0 3 2 8 GAME 2 3 2 3 2 8 GAME 3 4 0 1 3 8 GAME 4 1 3 3 3 3 8 GAME 5 2 0 0 2 2 8 GAME 6 2 0 0 2 3 8 GAME 7 2 2 4 1 1 8 GAME 8 3 1 2 3 1 8 GAME 9 4 1 5 1 8 GAME 10 1 4 4 2 8 GAME 11 2 0 0 4 2 8 GAME 12 2 1 1 1 2 8 GAME 13 3 6 1 2 8 GAME 14 2 6 3 8 GAME 15 3 6 2 3 8 GAME 16 1 1 4 1 2 8 GAME ...
output:
NRBBNKQR RNBBQKRN NRNKBRQB BBRKRNNQ BBNNQRKR QBBRKNNR NRBBNKQR RBBNQKRN BBNQRKNR BBNRQKRN NBBRKQNR NRBBNKQR BNRBNKRQ BRNKQBNR BBNNRKQR NBBRKNQR NRBBNKQR BRNNKBQR RBQNBNKR BBNQRKNR BBNNQRKR QBNRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNKBNR BBNNQRKR NBQRKNBR NRBBNKQR RNBBQKRN BRKQNRNB BQRNKBNR BBNNQRKR NBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 109ms
memory: 11164kb
input:
GAME 1 3 2 6 4 8 GAME 2 2 2 2 3 5 8 GAME 3 4 4 2 4 8 GAME 4 4 5 2 8 GAME 5 3 2 4 4 8 GAME 6 5 5 2 8 GAME 7 2 1 1 4 3 8 GAME 8 3 2 5 2 8 GAME 9 4 2 5 8 GAME 10 3 3 4 3 3 8 GAME 11 4 3 1 3 8 GAME 12 3 4 3 2 8 GAME 13 3 1 2 2 2 8 GAME 14 4 3 1 5 8 GAME 15 5 3 2 1 8 GAME 16 4 5 1 8 GAME 17 5 5 4 8 GAME ...
output:
NRBBNKQR RBBNQKRN BBNQRKNR BBNNRKQR BBRQNKNR NRBBNKQR RNBBQKRN QNRBKNBR RBNNBQKR BBNNQRKR BBRNQKNR NRBBNKQR BNRBNKRQ BBNRKNRQ BBNNQRKR BBRNNKQR NRBBNKQR BNRBNKRQ BBNNRKRQ BQRBNKNR NRBBNKQR RBBNQKRN BBNQRKNR BRNBQKRN BNRBQKNR NRBBNKQR BQRBNNKR NQBBRNKR BNRBNKQR NRBBNKQR RNBBQKRN NRNKBRQB BBNQRKNR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 116ms
memory: 11100kb
input:
GAME 1 2 2 3 3 3 8 GAME 2 2 3 4 4 8 GAME 3 2 3 3 3 3 8 GAME 4 1 4 4 3 8 GAME 5 1 3 6 2 8 GAME 6 1 3 4 4 2 8 GAME 7 4 3 3 6 8 GAME 8 3 1 6 5 8 GAME 9 4 3 4 3 8 GAME 10 3 1 3 2 4 8 GAME 11 3 0 3 5 8 GAME 12 2 1 2 5 6 8 GAME 13 5 5 5 8 GAME 14 5 4 0 8 GAME 15 6 1 1 8 GAME 16 4 1 5 3 8 GAME 17 5 3 2 2 8...
output:
NRBBNKQR RNBBQKRN QNRBKNBR BNNQRBKR BBNNQRKR RQNBBNKR NRBBNKQR RNBBQKRN RQKBNNBR QNRBBKNR RNQBBNKR NRBBNKQR RNBBQKRN RQKBNNBR BBRNNQKR BBNNQRKR RNNBBQKR NRBBNKQR BRNNKBQR QNBNRBKR BBNQNRKR RQNNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBNNRKQR RNQNBBKR NRBBNKQR BRNNKBQR RBQNBNKR BBNQNRKR BBNNRKQR RNNQBBKR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed