QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647488 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 189ms | 3992kb | C++20 | 2.5kb | 2024-10-17 14:24:56 | 2024-10-17 14:25:10 |
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;
vector<string> v;
set<string> s;
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;
s.insert(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;
}
void doTest(ll testID) {
backtrack(1, 0, 0, 0, 0, 0);
for (auto x: s) v.push_back(x);
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; ld cur = 1e18;
if (i == 1) chs = "NNRKRBBQ";
else {
for (auto x: cv) {
map<ll, ll> pp; for (auto y: cv) pp[get(x, y)] ++;
ld avg = 0, j = 0; for (auto [x, y]: pp) avg += y, j ++; avg /= pp.size();
ld tmp = 0; for (auto [x, y]: pp) tmp += (ld)(y - avg) * (y - avg) / pp.size();
if (tmp < cur) cur = tmp, 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: 0ms
memory: 3732kb
input:
GAME 1 1 2 1 2 0 8 END
output:
NNRKRBBQ NRBBNQKR QBBNRKNR RQNBKNBR QRKRNNBB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 189ms
memory: 3992kb
input:
GAME 1 1 2 1 2 0 8 GAME 2 1 1 0 1 8 GAME 3 2 1 2 2 3 8 GAME 4 2 0 2 0 3 8 GAME 5 2 0 4 2 8 GAME 6 3 1 5 8 GAME 7 2 3 2 4 5 8 GAME 8 2 2 0 0 4 8 GAME 9 3 1 2 1 8 GAME 10 1 0 1 4 4 8 GAME 11 1 1 1 2 3 8 GAME 12 1 0 3 1 2 8 GAME 13 3 3 1 2 3 8 GAME 14 3 2 1 5 8 GAME 15 4 2 4 8 GAME 16 2 1 4 2 4 8 GAME ...
output:
NNRKRBBQ NRBBNQKR QBBNRKNR RQNBKNBR QRKRNNBB RKRBBQNN NNRKRBBQ NRBBNQKR BQNRKBNR QBBNRKRN RKRBBNQN NNRKRBBQ NRNQBBKR RBQKNNBR NBBRKNRQ BNRBKNQR RKRBBNNQ NNRKRBBQ NRNQBBKR BBRKNQRN BNQNRKRB RBKRNNBQ RKRBQNBN NNRKRBBQ NRNQBBKR BBRKNQRN BNRNKQRB RKRBNQBN NNRKRBBQ NRNQKBBR RNKBNRBQ RKRBNNBQ NNRKRBBQ NRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: -100
Time Limit Exceeded
input:
GAME 1 0 2 2 3 2 8 GAME 2 0 3 2 1 2 8 GAME 3 0 4 0 8 GAME 4 1 3 3 3 8 GAME 5 1 2 1 6 8 GAME 6 1 4 3 2 8 GAME 7 1 1 3 2 0 8 GAME 8 1 1 4 8 GAME 9 1 1 3 3 2 8 GAME 10 2 2 1 4 8 GAME 11 2 4 5 4 8 GAME 12 2 3 5 2 8 GAME 13 0 0 5 8 GAME 14 0 1 5 8 GAME 15 1 0 1 8 GAME 16 1 0 2 4 8 GAME 17 1 2 1 2 4 8 GAM...
output:
NNRKRBBQ BRNBNKQR RBBNNQKR RKNNBRQB RBNQBKRN RKQBBNNR NNRKRBBQ BRNBNKQR QBBRNKNR BBNRKRQN QRNNBKRB RKNBBQNR NNRKRBBQ BRNBNKQR BRQNNKRB RKNBBNQR NNRKRBBQ NRBBNQKR BQNBRNKR BRKBNNRQ RKQBNNBR NNRKRBBQ NRBBNQKR QBBNRKNR RQNBKNBR RKNBQNBR NNRKRBBQ NRBBNQKR NBNRBQKR NRKBBQRN RKNBNQBR NNRKRBBQ NRBBNQKR BQN...