QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#875395 | #7179. Fischer's Chess Guessing Game | shinonome_ena# | AC ✓ | 9ms | 11772kb | C++23 | 2.1kb | 2025-01-29 17:38:14 | 2025-01-29 17:38:14 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define MAX 505050
#define INF 1e18
vector<int> lst[960];
int N = 960;
int mp[1010][1010];
int adj[MAX][9];
int cr[MAX];
int ans[MAX];
string S = "KQRBN";
int make_tree(int loc, vector<int>& lst, int dep = 0) {
if (dep >= 6) return -1;
if (lst.size() == 1) {
ans[loc] = lst[0];
return loc;
}
ans[loc] = -1;
int i, c;
for (auto c : lst) {
vector<int> ch[9];
for (i = 0; i < 9; i++) ch[i] = vector<int>();
for (auto v : lst) ch[mp[c][v]].push_back(v);
int v = loc + 1;
int chk = 1;
for (i = 0; i < 9; i++) if (ch[i].size()) {
int res = make_tree(v, ch[i], dep + 1);
if (!~res) {
chk = 0;
break;
}
adj[loc][i] = v;
v = res + 1;
}
if (!chk) continue;
cr[loc] = c;
return v;
}
return -1;
}
void query(int loc) {
if (~ans[loc]) {
for (auto v : lst[ans[loc]]) cout << S[v];
cout << endl;
int x;
cin >> x;
assert(x == 8);
return;
}
for (auto v : lst[cr[loc]]) cout << S[v];
cout << endl;
int x;
cin >> x;
if (x == 8) return;
query(adj[loc][x]);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
vector<int> v = { 0, 1, 2, 2, 3, 3, 4, 4 };
int i, j, k;
int cnt = 0;
while (1) {
int k, r1, r2, b1, b2;
k = r1 = r2 = b1 = b2 = -1;
for (i = 0; i < 8; i++) {
if (v[i] == 0) k = i;
if (v[i] == 2) r2 = r1, r1 = i;
if (v[i] == 3) b2 = b1, b1 = i;
}
if (((b1 ^ b2) & 1) && r2 < k && k < r1) lst[cnt++] = v;
if (!next_permutation(v.begin(), v.end())) break;
}
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < 8; k++) mp[i][j] += lst[i][k] == lst[j][k];
}
}
vector<int> bum;
for (i = 0; i < N; i++) bum.push_back(i);
int M = make_tree(1, bum);
while (1) {
string s;
cin >> s;
if (s[0] == 'G') {
int a;
cin >> a;
query(1);
}
else break;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 11656kb
input:
GAME 1 3 1 3 3 8 END
output:
QRKRBBNN QRKBNNBR QBRNBKRN QNRKBRNB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 5ms
memory: 11660kb
input:
GAME 1 3 1 3 3 8 GAME 2 2 1 3 4 8 GAME 3 2 1 2 4 8 GAME 4 1 3 2 2 8 GAME 5 1 3 1 4 4 8 GAME 6 0 6 8 GAME 7 4 0 8 GAME 8 3 0 6 8 GAME 9 3 0 5 8 GAME 10 2 2 1 1 0 8 GAME 11 2 1 1 6 8 GAME 12 1 2 5 8 GAME 13 2 1 3 3 8 GAME 14 2 0 6 8 GAME 15 1 3 0 8 GAME 16 0 5 5 8 GAME 17 0 4 8 GAME 18 0 4 6 8 GAME 19...
output:
QRKRBBNN QRKBNNBR QBRNBKRN QNRKBRNB RKRBBQNN QRKRBBNN QRBKNNRB QNRBKRBN RKBBQRNN RKRBBNQN QRKRBBNN QRBKNNRB QNRBKRBN RKNBBQRN RKRBBNNQ QRKRBBNN QBRKNNBR QNBBRNKR BQRKRNNB RKRBQNBN QRKRBBNN QBRKNNBR QNBBRNKR RKNQNBBR RKQRNNBB RKRBNQBN QRKRBBNN RKQBNNBR RKRBNNBQ QRKRBBNN QRKRNNBB RKRQBBNN QRKRBBNN QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 8ms
memory: 11548kb
input:
GAME 1 2 1 1 5 8 GAME 2 2 0 2 8 GAME 3 1 2 4 5 8 GAME 4 0 8 GAME 5 0 6 5 5 8 GAME 6 0 6 5 5 6 8 GAME 7 3 1 2 1 5 8 GAME 8 3 1 1 1 6 8 GAME 9 2 0 4 8 GAME 10 1 3 1 6 8 GAME 11 1 3 1 8 GAME 12 1 2 2 3 2 8 GAME 13 5 3 2 8 GAME 14 4 3 1 8 GAME 15 4 3 0 8 GAME 16 3 3 1 2 8 GAME 17 3 3 0 8 GAME 18 2 2 4 2...
output:
QRKRBBNN QRBKNNRB QNRBKRBN RKQNBRNB RKQBBNNR QRKRBBNN QRBKNNRB RKQNRBBN RKNBBQNR QRKRBBNN QBRKNNBR RKBRNNQB RKBBQNNR RKNBBNQR QRKRBBNN RKQBNNBR QRKRBBNN RKQBNNBR RKRBNNBQ RKBBNNQR RKNBQNBR QRKRBBNN RKQBNNBR RKRBNNBQ RKBBNNQR RKNBQNBR RKNBNQBR QRKRBBNN QRKBNNBR QBRNBKRN BRNKQBRN RKQBBRNN RKQNBBNR QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 9ms
memory: 11656kb
input:
GAME 1 8 GAME 2 6 4 5 5 8 GAME 3 6 5 4 8 GAME 4 6 8 GAME 5 5 3 2 5 3 8 GAME 6 4 5 3 5 8 GAME 7 6 4 8 GAME 8 5 3 3 5 8 GAME 9 4 5 3 3 8 GAME 10 4 8 GAME 11 3 4 2 2 5 8 GAME 12 3 4 1 3 8 GAME 13 4 2 4 3 1 8 GAME 14 3 4 4 8 GAME 15 3 4 3 1 8 GAME 16 5 3 5 3 8 GAME 17 4 2 2 3 1 8 GAME 18 4 2 2 3 0 8 GAM...
output:
QRKRBBNN QRKRBBNN QRKRBNNB QRKRNBBN QRKNBBRN NRKRBBQN QRKRBBNN QRKRBNNB QRKBBRNN NRKRBBNQ QRKRBBNN QRKRBNNB QRKRBBNN QRKBBNRN QRBKRBNN RBKRBQNN RNKRBBQN NRKRBQNB QRKRBBNN QRKRNNBB QRKBRNBN BRKRQNNB NRKRBNQB QRKRBBNN QRKRBNNB QRKRNBBN QRKRBBNN QRKBBNRN QRBKRBNN BRKRNBQN NRKRQBBN QRKRBBNN QRKRNNBB QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 7ms
memory: 11772kb
input:
GAME 1 2 1 2 3 1 8 GAME 2 2 1 3 2 2 8 GAME 3 1 2 1 2 8 GAME 4 0 3 3 8 GAME 5 0 4 4 3 8 GAME 6 0 2 2 6 8 GAME 7 2 2 1 0 8 GAME 8 1 3 1 2 6 8 GAME 9 1 3 1 2 5 8 GAME 10 3 0 4 3 8 GAME 11 2 1 2 4 2 8 GAME 12 2 1 1 4 3 8 GAME 13 1 4 1 4 2 8 GAME 14 1 3 0 2 2 8 GAME 15 0 3 1 8 GAME 16 1 2 4 3 8 GAME 17 1...
output:
QRKRBBNN QRBKNNRB QNRBKRBN RKNBBQRN BRNBKQNR RQNKRBBN QRKRBBNN QRBKNNRB QNRBKRBN RKBBQRNN BNQRKRNB RNQKRBBN QRKRBBNN QBRKNNBR RKBRNNQB RBQNKRBN RNNKRBBQ QRKRBBNN RKQBNNBR RKBNQNRB RQNKRNBB QRKRBBNN RKQBNNBR RKRNQNBB RKBQNNRB RNQKRNBB QRKRBBNN RKQBNNBR RQBNKNRB RNNKQRBB RNNKRQBB QRKRBBNN QRBKNNRB QBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 6ms
memory: 9732kb
input:
GAME 1 4 3 8 GAME 2 3 1 2 6 4 8 GAME 3 2 5 3 2 3 8 GAME 4 2 8 GAME 5 1 2 3 8 GAME 6 1 2 3 6 8 GAME 7 5 5 8 GAME 8 4 1 3 5 8 GAME 9 3 1 2 5 8 GAME 10 3 3 5 8 GAME 11 2 5 2 5 8 GAME 12 2 4 0 8 GAME 13 3 3 3 3 8 GAME 14 3 2 2 0 8 GAME 15 2 3 3 1 8 GAME 16 4 3 6 8 GAME 17 3 2 3 2 8 GAME 18 2 4 3 8 GAME ...
output:
QRKRBBNN QRKRNNBB QRBKNBRN QRKRBBNN QRKBNNBR QBRNBKRN BRNKQBRN BRNQKBRN NRBKQBRN QRKRBBNN QRBKNNRB QRBBNNKR QRNKRNBB QNBRNKRB NRBKNBRQ QRKRBBNN QRBKNNRB QRKRBBNN QBRKNNBR RKBRNNQB NRBKQNRB QRKRBBNN QBRKNNBR RKBRNNQB NRBKQNRB NRBKNQRB QRKRBBNN QRKBBNRN QRNKBBRN QRKRBBNN QRKRNNBB QBRKBRNN BRQKRBNN NRQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 7ms
memory: 11656kb
input:
GAME 1 2 1 3 5 8 GAME 2 1 1 2 5 3 8 GAME 3 1 1 3 2 3 8 GAME 4 1 2 1 8 GAME 5 1 2 1 6 8 GAME 6 0 2 3 8 GAME 7 2 1 4 2 5 8 GAME 8 1 0 3 1 8 GAME 9 1 0 4 1 8 GAME 10 1 0 6 5 8 GAME 11 1 0 5 3 8 GAME 12 0 1 6 8 GAME 13 1 1 1 2 8 GAME 14 1 1 1 1 3 8 GAME 15 0 3 1 5 8 GAME 16 0 2 5 8 GAME 17 0 3 3 3 3 8 G...
output:
QRKRBBNN QRBKNNRB QNRBKRBN RKBBQRNN RBBQKRNN QRKRBBNN QBRKNNBR RKBQRNNB RBBNQKRN RQBBNKRN RBBNKRQN QRKRBBNN QBRKNNBR RKBQRNNB RKBBNQRN RKNNRBBQ RBBNKRNQ QRKRBBNN QBRKNNBR RKBRNNQB RBQNKRBN QRKRBBNN QBRKNNBR RKBRNNQB RBQNKRBN RBNQKRBN QRKRBBNN RKQBNNBR RQBNKNRB RBNNKRBQ QRKRBBNN QRBKNNRB QNRBKRBN QNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 5ms
memory: 11656kb
input:
GAME 1 2 3 8 GAME 2 1 3 3 3 1 8 GAME 3 1 2 0 1 8 GAME 4 3 4 3 5 8 GAME 5 2 1 2 0 2 8 GAME 6 2 1 2 1 4 8 GAME 7 2 0 1 1 8 GAME 8 1 2 1 5 2 8 GAME 9 1 2 0 4 3 8 GAME 10 2 0 1 3 8 GAME 11 1 1 0 2 8 GAME 12 1 1 1 1 2 8 GAME 13 1 1 2 1 4 8 GAME 14 1 1 3 0 8 GAME 15 0 0 3 8 GAME 16 2 1 6 8 GAME 17 1 3 0 2...
output:
QRKRBBNN QRBKNNRB QRNBKNBR QRKRBBNN QBRKNNBR QNBBRNKR RBQNBNKR RBBKRNQN NRQBKNBR QRKRBBNN QBRKNNBR RKBRNNQB BBQNRKNR NRNBKQBR QRKRBBNN QRKBNNBR QRBBKNRN QRBNNBKR QRNNKBBR QRKRBBNN QRBKNNRB QNRBKRBN RKNBBQRN BNRKQBNR NRQNKBBR QRKRBBNN QRBKNNRB QNRBKRBN RKNBBQRN RNBQKBNR NRNQKBBR QRKRBBNN QRBKNNRB RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 5ms
memory: 11652kb
input:
GAME 1 3 3 4 5 8 GAME 2 2 1 1 1 2 8 GAME 3 1 3 3 3 4 8 GAME 4 2 2 8 GAME 5 1 4 3 3 3 8 GAME 6 1 3 1 3 4 8 GAME 7 4 2 4 1 8 GAME 8 3 1 0 4 8 GAME 9 2 1 2 0 3 8 GAME 10 3 3 1 8 GAME 11 2 0 2 2 4 8 GAME 12 2 0 3 0 8 GAME 13 1 2 3 2 1 8 GAME 14 1 1 2 8 GAME 15 0 2 4 8 GAME 16 2 1 1 4 8 GAME 17 2 1 1 2 2...
output:
QRKRBBNN QRKBNNBR QRBKRNNB QBRKBNNR QBBRKNNR QRKRBBNN QRBKNNRB QNRBKRBN RKQNBRNB NRNBBKQR NBBRKQNR QRKRBBNN QBRKNNBR QNBBRNKR RBQNBNKR RBBKRNQN NBBRKNQR QRKRBBNN QRBKNNRB QBNRKNBR QRKRBBNN QBRKNNBR QBBNRNKR RBKNNQBR RBNKBNQR NBQRKNBR QRKRBBNN QBRKNNBR QNBBRNKR RKNQNBBR RBNKRQBN NBNRKQBR QRKRBBNN QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 7ms
memory: 11652kb
input:
GAME 1 1 4 2 2 8 GAME 2 1 3 1 1 8 GAME 3 0 2 1 8 GAME 4 1 3 2 4 8 GAME 5 1 2 0 4 8 GAME 6 0 3 0 4 8 GAME 7 3 2 3 8 GAME 8 2 0 0 3 8 GAME 9 1 3 1 1 5 8 GAME 10 1 6 6 8 GAME 11 0 3 0 2 6 8 GAME 12 0 2 1 5 8 GAME 13 3 3 2 3 8 GAME 14 2 0 0 2 8 GAME 15 1 2 1 0 2 8 GAME 16 1 5 4 8 GAME 17 0 4 2 2 3 8 GAM...
output:
QRKRBBNN QBRKNNBR QBBNRNKR RQKBNNBR BBRQNKNR QRKRBBNN QBRKNNBR QNBBRNKR RKNQNBBR BBRNQKNR QRKRBBNN RKQBNNBR RQBNKNRB BBRNNKQR QRKRBBNN QBRKNNBR QNBBRNKR BQRKRNNB BQRBNKNR QRKRBBNN QBRKNNBR RKBRNNQB BBQNRKNR BNRBQKNR QRKRBBNN RKQBNNBR RKBNQNRB BQNBNRKR BNRBNKQR QRKRBBNN QRKBNNBR QRBNKRNB QBRNBKNR QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 7ms
memory: 11656kb
input:
GAME 1 1 2 2 8 GAME 2 1 2 2 6 8 GAME 3 1 1 1 3 0 8 GAME 4 2 0 3 3 8 GAME 5 2 0 4 5 8 GAME 6 2 0 2 4 8 GAME 7 1 3 4 3 8 GAME 8 1 2 1 0 8 GAME 9 1 2 1 0 6 8 GAME 10 2 2 1 1 8 GAME 11 2 2 2 4 0 8 GAME 12 2 1 0 4 3 8 GAME 13 2 5 8 GAME 14 1 2 2 4 1 8 GAME 15 1 2 2 3 4 8 GAME 16 3 4 3 8 GAME 17 2 3 2 1 8...
output:
QRKRBBNN QBRKNNBR RKBRNNQB RQNBBNKR QRKRBBNN QBRKNNBR RKBRNNQB RQNBBNKR RNQBBNKR QRKRBBNN QBRKNNBR RKBQRNNB RBNNBKRQ BRQNNKRB RNNBBQKR QRKRBBNN QRBKNNRB RKQNRBBN RKNBBRQN RQNNBBKR QRKRBBNN QRBKNNRB RKQNRBBN RKNNBBQR RNQNBBKR QRKRBBNN QRBKNNRB RKQNRBBN RKNBBQNR RNNQBBKR QRKRBBNN QBRKNNBR QNBBRNKR RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed