QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714020 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 1982ms | 3920kb | C++20 | 2.6kb | 2024-11-05 21:15:44 | 2024-11-05 21:15:44 |
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 ++) {
if (i == 7) {cout << 1 / 0;}
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(_);
}
詳細信息
Test #1:
score: 100
Accepted
time: 22ms
memory: 3900kb
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: 1969ms
memory: 3920kb
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: 1927ms
memory: 3920kb
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: 1982ms
memory: 3688kb
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: 1973ms
memory: 3688kb
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: -100
Time Limit Exceeded
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...