QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647528 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 220ms | 4048kb | C++20 | 3.0kb | 2024-10-17 14:35:43 | 2024-10-17 14:35:43 |
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;
}
mt19937_64 rng(static_cast<ll>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));
ll rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
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 ++) {
const string fuck[] = {
"RBNKQRBN",
"BQRKNBNR",
"RKRBBQNN",
"NNRKRBBQ",
"NNBBRKQR",
"RKQBBNNR",
"NQNRBKRB",
"NQNRBKRB"
};
string chs; ld cur = 1e18;
if (i == 1) chs = fuck[rand(0, 7)];
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: 5ms
memory: 3948kb
input:
GAME 1 1 2 3 1 3 8 END
output:
NNBBRKQR RKNNQBBR RNQKBBRN BNRNKBRQ RBKNBRQN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 181ms
memory: 3864kb
input:
GAME 1 1 2 3 1 3 8 GAME 2 1 1 0 1 8 GAME 3 1 2 3 4 4 8 GAME 4 5 8 GAME 5 0 1 2 3 8 GAME 6 0 1 1 2 3 8 GAME 7 2 3 2 4 5 8 GAME 8 2 2 5 4 8 GAME 9 1 2 0 5 8 GAME 10 1 0 1 4 4 8 GAME 11 2 0 1 2 8 GAME 12 1 0 3 1 2 8 GAME 13 4 1 4 4 8 GAME 14 4 1 3 2 8 GAME 15 0 0 1 5 8 GAME 16 2 0 5 4 8 GAME 17 2 0 1 2...
output:
NNBBRKQR RKNNQBBR RNQKBBRN BNRNKBRQ RBKNBRQN RKRBBQNN NNRKRBBQ NRBBNQKR BQNRKBNR QBBNRKRN RKRBBNQN RBNKQRBN RQBNKNRB RNKRBQNB RKBRNBNQ RKQNBBNR RKRBBNNQ RKRBBQNN RKRBQNBN NQNRBKRB BNRNQBKR BRQBKRNN RKBQRBNN RKRBNQBN NQNRBKRB BNRNQBKR BRQBKRNN RBBKNQNR QBRKRNBN RKRBNNBQ NNRKRBBQ NRNQBBKR RNBNQBKR RQN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 200ms
memory: 3768kb
input:
GAME 1 8 GAME 2 2 2 5 8 GAME 3 3 8 GAME 4 2 4 3 3 8 GAME 5 1 2 2 3 1 8 GAME 6 1 2 1 3 2 8 GAME 7 1 2 3 4 8 GAME 8 2 4 0 8 GAME 9 4 1 4 2 5 8 GAME 10 2 2 1 4 8 GAME 11 3 1 1 1 4 8 GAME 12 2 2 2 2 1 8 GAME 13 2 0 1 6 8 GAME 14 1 1 0 3 8 GAME 15 1 3 3 2 2 8 GAME 16 0 1 6 5 8 GAME 17 0 0 2 5 8 GAME 18 1...
output:
RKQBBNNR NQNRBKRB NRNQKBBR RBNNBQKR RKNBBQNR NNBBRKQR RKNBBNQR BQRKNBNR RNBBNQKR RKBRNQNB RBBNNKQR RKQBNNBR NQNRBKRB BRNQKBNR QRBBKNRN RKBRQBNN BNRKQBRN RKNBQNBR NQNRBKRB BRNQKBNR QRBBKNRN RKBQNRNB RBBNQKNR RKNBNQBR RBNKQRBN RQBNKNRB RNKRBQNB RKBRNBNQ RKQNBBNR NQNRBKRB NRNQKBBR NRQNKRBB RKNQBBNR RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 197ms
memory: 4044kb
input:
GAME 1 2 2 1 1 4 8 GAME 2 2 4 1 3 8 GAME 3 1 1 2 1 8 GAME 4 0 1 3 3 8 GAME 5 0 4 4 2 8 GAME 6 1 2 0 6 8 GAME 7 2 2 2 4 8 GAME 8 0 3 3 5 8 GAME 9 2 4 3 4 8 GAME 10 2 2 0 5 2 8 GAME 11 3 0 1 3 8 GAME 12 1 1 1 5 4 8 GAME 13 2 1 3 3 8 GAME 14 2 0 8 GAME 15 0 1 4 8 GAME 16 3 1 5 8 GAME 17 2 0 3 6 8 GAME ...
output:
NQNRBKRB NRNQKBBR RBNNBQKR BRNKRNQB NRKBBRNQ QRKRBBNN RKRBBQNN NRNBBKQR NQRBNKBR QRNKBBNR NRKRBBQN NNBBRKQR RKNNQBBR BNRKNBRQ BRNBKQRN NRKRBBNQ NNRKRBBQ BRNBNKQR RQKBBNRN RBKNBQNR QRKRBNNB RBNKQRBN BRKNNQRB NRQNBKRB BNQRNKRB NRKRBQNB NNRKRBBQ NRBBNQKR QBBNRKNR NRKQBNRB NRKRBNQB NNRKRBBQ NRNQBBKR NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 204ms
memory: 4048kb
input:
GAME 1 1 2 1 2 0 8 GAME 2 2 0 0 1 5 8 GAME 3 1 2 0 6 8 GAME 4 2 1 4 0 8 GAME 5 1 2 3 8 GAME 6 1 1 1 3 2 8 GAME 7 6 4 5 8 GAME 8 2 3 4 4 8 GAME 9 2 0 4 3 8 GAME 10 1 0 3 1 8 GAME 11 2 1 0 2 4 8 GAME 12 2 1 0 3 8 GAME 13 6 6 8 GAME 14 2 1 4 3 8 GAME 15 6 8 GAME 16 1 2 2 5 2 8 GAME 17 1 1 5 6 8 GAME 18...
output:
RKQBBNNR NRKQNBBR NRBKQNRB NBQRKRBN QBBNNRKR RQNKRBBN RKRBBQNN NRNBBKQR BBRNKRNQ RKBQNNRB RNKRQBBN RNQKRBBN NQNRBKRB BRNQKBNR QRBBKNRN RKNNRBBQ RNNKRBBQ RKQBBNNR RBBNNQKR QRBKRNNB QRBBKRNN RQNKRNBB BQRKNBNR RKNBBNQR RNKQBRNB RNQKRNBB RKQBBNNR NRKQNBBR RBBNNKRQ BRNKQNRB BQRKNRNB RNNKRQBB RBNKQRBN RBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 192ms
memory: 3968kb
input:
GAME 1 1 2 3 2 2 8 GAME 2 2 3 4 5 8 GAME 3 2 3 3 3 3 8 GAME 4 2 1 4 2 8 GAME 5 2 2 6 5 8 GAME 6 3 1 1 8 GAME 7 3 5 4 4 8 GAME 8 2 0 2 3 4 8 GAME 9 4 4 4 2 8 GAME 10 2 5 2 3 8 GAME 11 1 3 1 2 3 8 GAME 12 5 5 5 8 GAME 13 2 3 2 2 8 GAME 14 3 5 4 8 GAME 15 1 5 5 4 8 GAME 16 0 2 3 3 1 8 GAME 17 3 1 4 3 4...
output:
RKRBBQNN RBQKNNBR NRBBNKQR QBBNRKNR NRQNBBKR QRBKNBRN NQNRBKRB NRNQKBBR NRBBQKNR NRBBKQRN NRBKQBRN NQNRBKRB NRNQKBBR NRBBQKNR NRBNKRQB NQBNRBKR NRBKNBRQ NQNRBKRB NRNQKBBR BRKNNQRB RNKRNQBB QRBKNNRB NNRKRBBQ NRNQBBKR NRBKNQRB NRBKNRQB NRBKQNRB NQNRBKRB RQNKBBNR NBNRKRBQ NRBKNQRB RBNKQRBN QRNKNBBR NRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 220ms
memory: 3744kb
input:
GAME 1 1 1 0 4 8 GAME 2 2 1 0 1 8 GAME 3 1 1 2 0 3 8 GAME 4 1 0 5 3 3 8 GAME 5 6 5 5 5 8 GAME 6 1 1 4 2 1 8 GAME 7 3 4 1 6 8 GAME 8 0 1 4 1 8 GAME 9 3 4 1 8 GAME 10 2 2 1 1 2 8 GAME 11 1 3 0 3 2 8 GAME 12 1 0 1 3 1 8 GAME 13 3 1 1 2 8 GAME 14 0 1 5 2 8 GAME 15 2 1 0 2 8 GAME 16 3 3 2 0 8 GAME 17 1 1...
output:
NNBBRKQR RKNNQBBR BNRKNBRQ NBQRKRBN RBBQKRNN RKRBBQNN NRNBBKQR BQRKNBNR RKNQRNBB RBBNKRQN NNRKRBBQ NRBBNQKR BQNRKBNR BRNKQNRB QBRNBKNR RBBNKRNQ NNRKRBBQ NRBBNQKR BBRNKRQN BBRNQKRN BQRNKRNB RBQNKRBN RBNKQRBN RBNKNRBQ RBNKBRQN RBNKRQBN RBNQKRBN RKQBBNNR NRKQNBBR RBBNNKRQ BBRKNNRQ NNBBRKRQ RBNNKRBQ RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 195ms
memory: 4044kb
input:
GAME 1 1 4 5 8 GAME 2 1 4 2 1 8 GAME 3 1 3 4 2 8 GAME 4 1 4 4 3 8 GAME 5 1 2 0 1 1 8 GAME 6 2 6 4 8 GAME 7 0 2 3 3 8 GAME 8 0 3 1 6 8 GAME 9 0 3 1 8 GAME 10 2 0 3 4 8 GAME 11 0 3 0 6 8 GAME 12 3 0 2 8 GAME 13 2 1 3 2 8 GAME 14 1 4 1 3 8 GAME 15 1 2 1 2 8 GAME 16 0 2 1 1 8 GAME 17 3 4 2 8 GAME 18 1 2...
output:
BQRKNBNR RKNBBNQR RNQBKNBR QRNBKNBR RKRBBQNN RBQKNNBR QNRKNBBR RBBNNKQR NRQBKNBR BQRKNBNR RKNBBNQR QBNRKNBR QBNNBRKR NRNBKQBR RKQBBNNR NRKQNBBR NRBNQBKR NNRKQBBR QRNNKBBR RBNKQRBN RQBNKNRB RNKRBQNB BQNBRNKR BBRNNKRQ NRQNKBBR NNBBRKQR NRNQBBKR NBNQBRKR NRNQKBBR NQNRBKRB BNRNQBKR BRQBKNNR RBBNKQNR BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 186ms
memory: 3800kb
input:
GAME 1 2 2 3 2 1 8 GAME 2 2 3 2 2 8 GAME 3 1 3 2 1 8 GAME 4 2 2 2 6 8 GAME 5 1 2 0 3 6 8 GAME 6 2 3 2 4 8 GAME 7 1 4 2 2 1 8 GAME 8 2 2 6 8 GAME 9 2 4 2 2 8 GAME 10 3 5 5 3 8 GAME 11 2 4 2 2 8 GAME 12 3 1 4 2 8 GAME 13 2 1 2 3 8 GAME 14 2 0 4 1 8 GAME 15 1 1 8 GAME 16 0 1 4 2 3 8 GAME 17 4 4 6 8 GAM...
output:
BQRKNBNR RNBBNQKR BRNBKNQR QRNNBBKR NQNBRKBR QBBRKNNR BQRKNBNR RNBBNQKR RKBQNRNB RBQNNKBR NBBRKQNR RBNKQRBN RQBNKNRB RKBRNQNB BQRKRNNB NBBRKNQR RKQBBNNR RBBNNQKR NRBQKBNR BBNRKNQR QBNRKNBR BQRKNBNR RKNBBNQR RNKQBRNB NBBNRKQR NBNRKQBR NBQRKNBR NNBBRKQR NRNQBBKR NRKNRBBQ QRNBKNBR NBNRKQBR NQNRBKRB BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: -100
Time Limit Exceeded
input:
GAME 1 2 2 1 0 3 8 GAME 2 2 3 1 5 8 GAME 3 4 2 3 5 8 GAME 4 3 2 2 8 GAME 5 2 1 1 3 8 GAME 6 5 8 GAME 7 3 1 3 2 8 GAME 8 2 4 2 8 GAME 9 1 1 2 4 8 GAME 10 1 4 5 8 GAME 11 1 4 4 2 8 GAME 12 2 1 1 2 4 8 GAME 13 2 1 0 6 8 GAME 14 4 3 4 5 8 GAME 15 3 2 1 2 8 GAME 16 1 1 1 2 3 3
output:
NNBBRKQR NRNQBBKR NQRKRBBN RKNBBRQN BBQNRNKR BBRQNKNR RKQBBNNR RBBNNQKR RBBQKNRN NBRNBKQR BBRNQKNR BQRKNBNR RQBNKBNR BRNQNBKR BBQRNKNR BBRNNKQR NNBBRKQR RKNBBNQR RNBQNBKR BQRBNKNR NNRKRBBQ NRNQBBKR RBQKNNBR BNRQKNRB BNRBQKNR NNBBRKQR BNRBNKQR RKRBBQNN RKBNNQRB RNQKBBNR NQRKBBRN QBRNBKNR NNRKRBBQ NRN...