QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710377 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 1808ms | 3920kb | C++20 | 2.6kb | 2024-11-04 19:37:20 | 2024-11-04 19:37:22 |
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 ++) {
string chs;
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ìm đỉnh của đồ thị
ll t = 0; for (int j = 0; j <= 8; j ++) t = max(t, pp[j]);
// Chọn đồ thị có đỉnh bé nhất
if (t < mx) mx = t, 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(_);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 3644kb
input:
GAME 1 3 1 5 8 END
output:
RQKNBBRN NRBKQBRN RKNBBRQN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 4 (1 test case)
Test #2:
score: 0
Accepted
time: 1774ms
memory: 3888kb
input:
GAME 1 3 1 5 8 GAME 2 3 1 6 8 GAME 3 2 1 2 3 8 GAME 4 2 3 4 4 8 GAME 5 2 2 3 5 8 GAME 6 1 1 2 5 8 GAME 7 4 2 4 8 GAME 8 5 5 5 8 GAME 9 4 3 2 8 GAME 10 2 1 4 1 8 GAME 11 3 0 1 8 GAME 12 3 0 2 3 3 8 GAME 13 3 2 0 3 8 GAME 14 4 1 6 8 GAME 15 3 1 2 2 8 GAME 16 1 3 2 4 2 8 GAME 17 2 3 3 4 8 GAME 18 2 2 2...
output:
RQKNBBRN NRBKQBRN RKNBBRQN RKRBBQNN RQKNBBRN NRBKQBRN RKNBBRQN RKRBBNQN RQKNBBRN RNNKQBBR NNRQBKRB QBRKBRNN RKRBBNNQ RQKNBBRN RNNKQBBR RBQKRNBN RNQBKRBN RKRBQNBN RQKNBBRN RNNKQBBR RQBBNNKR RKQBRNBN RKRBNQBN RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKRBNNBQ RQKNBBRN RNKBBNRQ QRKRBBNN RKRQBBNN RQKNBBRN RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 1750ms
memory: 3696kb
input:
GAME 1 2 2 4 3 8 GAME 2 2 3 1 8 GAME 3 2 3 2 2 2 8 GAME 4 1 1 2 6 6 8 GAME 5 1 1 2 8 GAME 6 1 1 2 6 8 GAME 7 4 2 3 8 GAME 8 3 1 4 8 GAME 9 4 2 2 2 8 GAME 10 3 1 2 2 6 8 GAME 11 2 5 4 8 GAME 12 3 2 2 4 8 GAME 13 4 3 2 3 8 GAME 14 4 4 3 3 8 GAME 15 3 0 3 5 8 GAME 16 3 2 0 8 GAME 17 3 1 2 5 8 GAME 18 2...
output:
RQKNBBRN RNNKQBBR RQBBNNKR RNBBKNRQ RKQBBNNR RQKNBBRN RNNKQBBR RBQKRNBN RKNBBQNR RQKNBBRN RNNKQBBR RBQKRNBN NRQKBBNR RBBNQKNR RKNBBNQR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKNBNQBR RKQBNNBR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RQKNBBRN RNBQKRNB NNRBBKQR RKNBQNBR RKNBNQBR RQKNBBRN RNKBBNRQ QRKRBBNN RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 1790ms
memory: 3584kb
input:
GAME 1 4 2 8 GAME 2 4 2 6 8 GAME 3 3 3 6 8 GAME 4 2 0 4 3 8 GAME 5 2 0 3 8 GAME 6 2 0 5 8 GAME 7 3 3 3 2 6 8 GAME 8 3 5 3 8 GAME 9 2 2 1 0 1 8 GAME 10 1 1 0 3 2 8 GAME 11 1 1 1 2 8 GAME 12 1 1 1 1 8 GAME 13 2 0 4 8 GAME 14 2 0 6 4 8 GAME 15 1 1 1 3 0 8 GAME 16 3 3 5 5 8 GAME 17 4 1 4 8 GAME 18 3 2 2...
output:
RQKNBBRN RNKBBNRQ QRKRBBNN RQKNBBRN RNKBBNRQ QRKRBBNN NRKRBBQN RQKNBBRN NRBKQBRN NRKQBBNR NRKRBBNQ RQKNBBRN RNNKQBBR BRKNRNQB BRKBRQNN QRKRBNNB RQKNBBRN RNNKQBBR BRKNRNQB NRKRBQNB RQKNBBRN RNNKQBBR BRKNRNQB NRKRBNQB RQKNBBRN NRBKQBRN NRKQBBNR RQBKNBNR BRKRNBQN QRKRNBBN RQKNBBRN NRBKQBRN NRNKBBRQ NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 1762ms
memory: 3660kb
input:
GAME 1 4 1 5 8 GAME 2 3 3 1 4 8 GAME 3 2 6 8 GAME 4 2 4 5 3 8 GAME 5 1 3 2 8 GAME 6 1 3 2 6 8 GAME 7 2 3 4 3 1 8 GAME 8 2 2 3 2 8 GAME 9 1 4 1 3 8 GAME 10 3 2 1 5 8 GAME 11 3 2 2 5 8 GAME 12 2 3 3 2 8 GAME 13 2 3 6 8 GAME 14 2 5 2 5 8 GAME 15 1 2 1 3 8 GAME 16 2 2 4 2 3 8 GAME 17 1 6 5 8 GAME 18 1 5...
output:
RQKNBBRN RNKBBNRQ RKQNRBBN RQNKRBBN RQKNBBRN NRBKQBRN NRKQBBNR RKNRQBBN RNQKRBBN RQKNBBRN RNNKQBBR RNNKRBBQ RQKNBBRN RNNKQBBR RBNKRQBN RBNNKQBR RQNKRNBB RQKNBBRN RNBQKRNB RNBBNKQR RNQKRNBB RQKNBBRN RNBQKRNB RNBBNKQR RNQKRNBB RNNKRQBB RQKNBBRN RNNKQBBR RBQKRNBN RNQBKRBN RNKQRNBB RBBKQRNN RQKNBBRN RNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 1808ms
memory: 3920kb
input:
GAME 1 3 6 5 8 GAME 2 3 8 GAME 3 2 2 2 1 8 GAME 4 1 2 1 2 4 8 GAME 5 1 2 2 8 GAME 6 1 2 1 1 1 8 GAME 7 4 2 5 3 8 GAME 8 4 2 4 3 8 GAME 9 3 5 8 GAME 10 2 2 1 3 8 GAME 11 2 1 4 4 4 8 GAME 12 2 2 0 6 8 GAME 13 1 1 1 6 8 GAME 14 1 1 1 8 GAME 15 1 0 2 3 2 8 GAME 16 1 2 4 3 8 GAME 17 1 2 5 2 8 GAME 18 1 1...
output:
RQKNBBRN NRBKQBRN NRBQKBRN QRBKNBRN RQKNBBRN NRBKQBRN RQKNBBRN RNNKQBBR RQBBNNKR RKBNQRNB NRBKNBRQ RQKNBBRN RNBQKRNB BNRKQBNR RKNRQNBB BRNQNKRB QRBKNNRB RQKNBBRN RNBQKRNB BNRKQBNR NRBKQNRB RQKNBBRN RNBQKRNB BNRKQBNR RKNRQNBB NBRNKRBQ NRBKNQRB RQKNBBRN RNKBBNRQ QRKRBBNN RKQRBBNN QRNKBBRN RQKNBBRN RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 1805ms
memory: 3660kb
input:
GAME 1 2 1 1 2 8 GAME 2 3 2 1 1 8 GAME 3 2 1 0 3 8 GAME 4 3 1 3 1 8 GAME 5 2 3 4 5 8 GAME 6 2 3 3 5 2 8 GAME 7 3 2 0 2 8 GAME 8 2 2 3 3 8 GAME 9 1 6 8 GAME 10 3 1 2 1 8 GAME 11 1 8 GAME 12 2 2 2 5 8 GAME 13 3 1 5 3 8 GAME 14 2 3 4 8 GAME 15 1 4 2 5 8 GAME 16 3 0 3 2 8 GAME 17 2 3 3 8 GAME 18 1 6 4 8...
output:
RQKNBBRN RNNKQBBR NNRQBKRB RKBNRNQB RBBQKRNN RQKNBBRN NRBKQBRN QRNNBKRB RNQKBBNR RBBNKRQN RQKNBBRN RNNKQBBR NNRQBKRB RKBBNRQN RBBNKRNQ RQKNBBRN NRBKQBRN RKNBBRQN RNNQBBKR RBQNKRBN RQKNBBRN RNNKQBBR RBQKRNBN RNQBKRBN RBNQKRBN RQKNBBRN RNNKQBBR RBQKRNBN RNQNKRBB RNQKBRNB RBNNKRBQ RQKNBBRN NRBKQBRN QRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 1794ms
memory: 3728kb
input:
GAME 1 0 2 4 5 8 GAME 2 0 3 4 3 8 GAME 3 0 1 1 2 8 GAME 4 2 4 2 1 3 8 GAME 5 2 3 2 5 8 GAME 6 1 2 2 2 8 GAME 7 1 4 1 2 8 GAME 8 2 0 3 0 8 GAME 9 1 3 0 3 4 8 GAME 10 2 0 1 3 1 8 GAME 11 1 3 3 0 8 GAME 12 0 1 6 8 GAME 13 2 0 3 2 8 GAME 14 0 1 8 GAME 15 1 4 3 5 8 GAME 16 2 1 1 1 2 8 GAME 17 1 3 0 3 8 G...
output:
RQKNBBRN BBQRNNKR QRBBNKNR NRBBKNQR QRNBKNBR RQKNBBRN BBQRNNKR NRBBNQKR NBRKNQBR NRQBKNBR RQKNBBRN BBQRNNKR BNRQKRNB NRBKRNQB NRNBKQBR RQKNBBRN RNNKQBBR RBNKRQBN RNKRQNBB NQRKNBBR QRNNKBBR RQKNBBRN RNNKQBBR RBQKRNBN NRQKBBNR NRQNKBBR RQKNBBRN RNBQKRNB BNRKQBNR NRBKQNRB NRNQKBBR RQKNBBRN RNBQKRNB QNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 1784ms
memory: 3708kb
input:
GAME 1 0 4 4 4 8 GAME 2 0 3 4 4 8 GAME 3 0 4 6 8 GAME 4 0 4 3 1 8 GAME 5 0 5 3 5 8 GAME 6 0 3 3 8 GAME 7 1 4 5 2 8 GAME 8 2 2 3 0 8 GAME 9 1 3 4 3 2 8 GAME 10 1 2 3 3 2 8 GAME 11 2 4 2 2 2 8 GAME 12 1 2 3 2 8 GAME 13 3 3 1 2 8 GAME 14 4 2 1 8 GAME 15 3 2 3 4 2 8 GAME 16 5 3 8 GAME 17 4 3 4 2 8 GAME ...
output:
RQKNBBRN BBQRNNKR NBBRNKQR NBBQRNKR QBBRKNNR RQKNBBRN BBQRNNKR NRBBNQKR NBRKNQBR NBBRKQNR RQKNBBRN BBQRNNKR NBBRNKQR NBBRKNQR RQKNBBRN BBQRNNKR NBBRNKQR BRQBNKNR QBNRKNBR RQKNBBRN BBQRNNKR BBNRNKQR NBBRQNKR NBQRKNBR RQKNBBRN BBQRNNKR NRBBNQKR NBNRKQBR RQKNBBRN RNBQKRNB QNBRKNRB NRBQKNRB QNBRKBNR RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: -100
Time Limit Exceeded
input:
GAME 1 0 4 4 3 8 GAME 2 1 1 3 1 8 GAME 3 1 0 5 5 8 GAME 4 1 1 4 2 4 8 GAME 5 0 2 4 2 8 GAME 6 0 3 3 1 8 GAME 7 2 1 3 2 0 8 GAME 8 1 2 3 1 8 GAME 9 2 1 4 3 8 GAME 10 1 0 4 3 4 8 GAME 11 0 3 3 4 8 GAME 12 1 0 5 8 GAME 13 1 2 4 2 8 GAME 14 2 1 4 2 3 8 GAME 15 1 1 8 GAME 16 0 2 5 3 8 GAME 17 1 0 2 3 8 G...
output:
RQKNBBRN BBQRNNKR NBBRNKQR NBBQRNKR BBRQNKNR RQKNBBRN RNBQKRNB NNRBBKQR NRBKNBQR BBRNQKNR RQKNBBRN RNBQKRNB BBRNQNKR NBRNQKBR BBRNNKQR RQKNBBRN RNBQKRNB NNRBBKQR NBRQBNKR BNRKNBQR BQRBNKNR RQKNBBRN BBQRNNKR QRBBNKNR NRBBKNQR BNRBQKNR RQKNBBRN BBQRNNKR NRBBNQKR NBNRKQBR BNRBNKQR RQKNBBRN RNNKQBBR NNR...