QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710382 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 1999ms | 3960kb | C++20 | 2.6kb | 2024-11-04 19:38:12 | 2024-11-04 19:38:17 |
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 ++) {
assert(i <= 6);
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: 21ms
memory: 3680kb
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: 1985ms
memory: 3960kb
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: 1931ms
memory: 3644kb
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: 1999ms
memory: 3640kb
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: -100
Time Limit Exceeded
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...