QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647501 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 190ms | 3872kb | C++20 | 2.8kb | 2024-10-17 14:30:09 | 2024-10-17 14:30: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;
}
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[] = {"NNRKRBBQ", "RBNKQRBN", "BQRKNBNR", "NRNBBQKR"};
string chs; ld cur = 1e18;
if (i == 1) chs = fuck[rand(0, 3)];
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: 4ms
memory: 3728kb
input:
GAME 1 2 3 6 4 8 END
output:
RBNKQRBN QRNBBKRN RKNBBQNR RKNBBNQR RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 185ms
memory: 3872kb
input:
GAME 1 2 3 3 3 1 8 GAME 2 2 2 1 2 8 GAME 3 2 2 2 3 0 8 GAME 4 1 3 1 4 2 8 GAME 5 3 2 1 3 8 GAME 6 3 1 5 8 GAME 7 1 3 3 4 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 3 5 5 8 GAME 12 1 0 3 1 2 8 GAME 13 0 1 2 1 8 GAME 14 4 4 3 3 8 GAME 15 0 1 4 2 5 8 GAME 16 2 0 5 4 8 GAME 17 0...
output:
BQRKNBNR RNBBNQKR RKBQNRNB RQKBNRBN RBNQNKBR RKRBBQNN NRNBBQKR RBQNBKNR RNBQNBKR QRKNBBRN RKRBBNQN BQRKNBNR RNBBNQKR BRNBKNQR QBRNBNKR QBNRNKBR RKRBBNNQ NRNBBQKR RKQNNBBR BQRKNBNR RKRNBNQB RBBNKNQR RKRBQNBN RBNKQRBN QRNKNBBR RBQKBNNR RQKNNRBB RKRBNQBN NNRKRBBQ NRNQKBBR RNKBNRBQ RKRBNNBQ NRNBBQKR RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 189ms
memory: 3796kb
input:
GAME 1 1 2 3 3 2 8 GAME 2 0 3 2 1 2 8 GAME 3 0 4 0 8 GAME 4 2 3 4 2 3 8 GAME 5 1 6 4 8 GAME 6 3 4 2 1 8 GAME 7 1 1 3 2 0 8 GAME 8 3 2 6 4 8 GAME 9 2 2 3 5 8 GAME 10 1 8 GAME 11 2 2 5 2 8 GAME 12 2 3 1 6 8 GAME 13 1 2 4 4 8 GAME 14 1 1 1 4 8 GAME 15 1 3 3 2 2 8 GAME 16 0 1 6 5 8 GAME 17 1 3 1 1 3 8 G...
output:
RBNKQRBN RQBNKNRB RNKRBQNB RKBRNBNQ NBBRKQNR RKQBBNNR NNRKRBBQ BRNBNKQR QBBRNKNR BBNRKRQN QRNNBKRB RKNBBQNR NNRKRBBQ BRNBNKQR BRQNNKRB RKNBBNQR NRNBBQKR RBQNBKNR BBQRNNKR NBBRNKQR BRQKNBNR RKQBNNBR BQRKNBNR RKNBBNQR RNKBBNQR RKNBQNBR RBNKQRBN QRNKNBBR NRQKNRBB BRNKRBQN RKNBNQBR NNRKRBBQ NRBBNQKR BQN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 167ms
memory: 3744kb
input:
GAME 1 1 0 0 6 8 GAME 2 2 4 1 2 8 GAME 3 3 0 5 5 8 GAME 4 2 2 0 1 6 8 GAME 5 0 4 4 2 8 GAME 6 1 2 0 6 8 GAME 7 2 2 2 4 8 GAME 8 3 3 2 2 8 GAME 9 2 0 2 2 1 8 GAME 10 1 2 1 2 8 GAME 11 0 2 0 5 8 GAME 12 3 0 4 3 8 GAME 13 1 3 3 4 8 GAME 14 1 3 1 0 8 GAME 15 2 1 2 5 8 GAME 16 1 1 1 2 4 8 GAME 17 1 2 2 4...
output:
RBNKQRBN RQBNKNRB BNNBRQKR NRKRBBQN QRKRBBNN NNRKRBBQ NRNQBBKR RNBQNBKR NRNBKQBR NRKRBBQN NRNBBQKR RNBBQNKR NRKQBRNB NRKQBBRN NRKRBBNQ NRNBBQKR RBQNBKNR RNBQNBKR NBRKBRQN QRKNBNRB 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: 140ms
memory: 3764kb
input:
GAME 1 4 4 5 5 8 GAME 2 0 2 2 2 1 8 GAME 3 2 2 1 5 5 8 GAME 4 4 3 1 4 8 GAME 5 1 2 3 8 GAME 6 4 3 2 8 GAME 7 6 4 5 8 GAME 8 0 2 2 3 8 GAME 9 0 3 2 0 8 GAME 10 1 0 3 1 8 GAME 11 6 5 8 GAME 12 2 4 2 2 8 GAME 13 6 6 8 GAME 14 8 GAME 15 3 2 0 1 8 GAME 16 3 2 3 0 8 GAME 17 2 0 1 3 8 GAME 18 2 0 2 2 8 GAM...
output:
NNRKRBBQ BRNKRBNQ RKNNRBBQ RBNKRNBQ RQNKRBBN NRNBBQKR BNRKQRNB RKBQRNNB RQKNNRBB QNBRNKRB RNQKRBBN BQRKNBNR RNBBNQKR BRNBKNQR RKNRNBBQ RBNKNRBQ RNNKRBBQ RBNKQRBN RNKNQRBB RBBNKRQN QRNKNRBB RQNKRNBB BQRKNBNR RKNBBNQR RNKQBRNB RNQKRNBB NNRKRBBQ BRNKRBNQ NRQKNBBR RNNKRQBB RBNKQRBN RBNKNRBQ NBRKQRBN RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 132ms
memory: 3804kb
input:
GAME 1 1 2 1 0 4 8 GAME 2 2 1 1 5 8 GAME 3 1 2 0 0 8 GAME 4 1 4 1 8 GAME 5 2 0 2 8 GAME 6 3 1 3 8 GAME 7 2 0 1 6 4 8 GAME 8 2 0 2 2 8 GAME 9 4 2 1 3 8 GAME 10 3 1 1 2 2 8 GAME 11 1 3 1 2 3 8 GAME 12 5 2 3 8 GAME 13 2 3 4 2 8 GAME 14 3 5 4 8 GAME 15 2 4 3 4 8 GAME 16 5 3 3 3 8 GAME 17 2 1 2 2 8 GAME ...
output:
NRNBBQKR RKQNNBBR RQKNBNRB NBRNKRBQ BRKRNBQN QRBKNBRN BQRKNBNR RNBBNQKR BNRQKNRB NRBKQRNB NRBKQBRN RBNKQRBN RQBNKNRB RNKRBQNB BQNBRNKR NRBKNBRQ RBNKQRBN RQBNKNRB BQRNKBRN QRBKNNRB NRNBBQKR RBQNBKNR BRNKRBQN NRBKQNRB NRNBBQKR RNBBQNKR NRKBNRBQ NRBKNQRB BQRKNBNR RNBBNQKR BRQNKRNB NRNKBBRQ NRNKRBBQ QRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 170ms
memory: 3800kb
input:
GAME 1 4 2 2 3 8 GAME 2 0 1 2 4 8 GAME 3 1 1 3 0 8 GAME 4 1 0 5 3 3 8 GAME 5 6 5 5 5 8 GAME 6 5 3 5 8 GAME 7 1 1 4 2 8 GAME 8 0 2 8 GAME 9 1 2 4 3 8 GAME 10 0 3 3 3 8 GAME 11 1 1 3 1 8 GAME 12 0 0 2 8 GAME 13 5 3 3 5 8 GAME 14 2 0 1 8 GAME 15 2 1 2 4 1 8 GAME 16 1 2 3 3 3 8 GAME 17 3 1 2 8 GAME 18 4...
output:
RBNKQRBN RNKNQRBB NBRKNRBQ QRNBKRBN RBBQKRNN NNRKRBBQ BRNBNKQR RQKBBNRN RBBQKNNR RBBNKRQN BQRKNBNR RKNBBNQR RBBQNKRN BNQBRKRN RBBNKRNQ NNRKRBBQ NRBBNQKR BBRNKRQN BBRNQKRN BQRNKRNB RBQNKRBN RBNKQRBN RBNKNRBQ RBNKBRQN RBNKRQBN RBNQKRBN RBNKQRBN RBBKNRQN RBNKRNBQ RBNNKRBQ NRNBBQKR RKQNNBBR QNRBKRBN NBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 190ms
memory: 3796kb
input:
GAME 1 1 3 4 4 8 GAME 2 1 2 0 3 3 8 GAME 3 2 4 1 8 GAME 4 2 3 2 2 2 8 GAME 5 1 2 0 1 1 8 GAME 6 4 3 8 GAME 7 1 0 6 8 GAME 8 2 0 4 4 8 GAME 9 3 1 1 8 GAME 10 2 2 2 4 8 GAME 11 2 2 1 2 2 8 GAME 12 1 0 2 2 3 8 GAME 13 0 5 8 GAME 14 0 6 5 4 8 GAME 15 1 3 1 5 8 GAME 16 2 0 3 1 5 8 GAME 17 4 2 5 4 8 GAME ...
output:
NNRKRBBQ NRBBNQKR BQNBRNKR RQNBNKBR QRNBKNBR RBNKQRBN RQBNKNRB RNKRBQNB BQNBRNKR BRNNKBQR NRQBKNBR NNRKRBBQ NRNQBBKR RNBQNBKR NRNBKQBR RBNKQRBN QRNBBKRN RKNBBQNR BRQBKRNN BRNKNQRB QRNNKBBR RBNKQRBN RQBNKNRB RNKRBQNB BQNBRNKR BBRNNKRQ NRQNKBBR NRNBBQKR NRKBRQBN NRNQKBBR NNRKRBBQ NRBBNQKR BBRNKRQN BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 171ms
memory: 3792kb
input:
GAME 1 2 2 3 2 1 8 GAME 2 2 3 2 2 8 GAME 3 2 2 2 2 8 GAME 4 1 3 8 GAME 5 2 2 1 2 8 GAME 6 3 3 4 8 GAME 7 1 2 0 2 2 8 GAME 8 0 0 2 8 GAME 9 0 0 4 3 8 GAME 10 2 1 1 5 8 GAME 11 3 1 2 5 8 GAME 12 2 2 3 3 8 GAME 13 0 2 4 1 8 GAME 14 0 1 3 3 0 8 GAME 15 1 1 6 8 GAME 16 1 3 0 8 GAME 17 0 2 2 3 8 GAME 18 0...
output:
BQRKNBNR RNBBNQKR BRNBKNQR QRNNBBKR NQNBRKBR QBBRKNNR BQRKNBNR RNBBNQKR RKBQNRNB RBQNNKBR NBBRKQNR NRNBBQKR RBQNBKNR RNBQNBKR RKNRBBQN NBBRKNQR BQRKNBNR RKNBBNQR QBNRKNBR NNRKRBBQ NRNQBBKR NRBKNQRB RNBNKBQR NBQRKNBR RBNKQRBN QRNKNBBR RBKNNQBR NBNRKQBR NRNBBQKR RKQNNBBR RQKNBNRB NNRKRBBQ NBQRKRBN QNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 177ms
memory: 3796kb
input:
GAME 1 1 2 4 4 6 8 GAME 2 2 1 4 1 4 8 GAME 3 4 2 3 5 8 GAME 4 6 4 8 GAME 5 4 2 2 3 8 GAME 6 4 1 3 8 GAME 7 1 1 1 2 2 8 GAME 8 1 0 1 6 8 GAME 9 3 1 1 3 8 GAME 10 3 2 4 3 8 GAME 11 2 3 3 3 8 GAME 12 3 2 2 0 8 GAME 13 2 2 0 3 8 GAME 14 4 2 3 3 8 GAME 15 3 2 8 GAME 16 3 2 5 2 8 GAME 17 3 3 0 5 8 GAME 18...
output:
NNRKRBBQ NRBBNQKR QBBNRKNR QBNRNKBR BBRNNKQR BBRQNKNR RBNKQRBN QRNBBKRN RBKNBQNR RNKQBRNB BBNRKQNR BBRNQKNR BQRKNBNR RQBNKBNR BRNQNBKR BBQRNKNR BBRNNKQR BQRKNBNR BNRKNBQR BQRBNKNR BQRKNBNR RQBNKBNR BRNQNBKR BQRNNKRB BNRBQKNR BQRKNBNR RQBNKBNR BNRKRQNB BNRBNKQR RBNKQRBN RQBNKNRB NRKBBQRN BNRBQNKR BRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: -100
Time Limit Exceeded
input:
GAME 1 5 8 GAME 2 4 1 4 2 8 GAME 3 2 3 6 5 8 GAME 4 3 8 GAME 5 2 4 1 4 8 GAME 6 2 6 5 4 8 GAME 7 4 2 5 5 8 GAME 8 2 3 3 4 8 GAME 9 6 4 8 GAME 10 1 4 2 8 GAME 11 4 2 8 GAME 12 4 1 2 5 8 GAME 13 4 2 4 5 8 GAME 14 1 6 5 5 8 GAME 15 2 6 8 GAME 16 3 4 3 8 GAME 17 0 2 3 3 8 GAME 18 4 2 2 4 8 GAME 19 1 1 3...
output:
NRNBBQKR RQNBBNKR NRNBBQKR NRKBRQBN NBRQBNKR NBNRBKQR RNQBBNKR RBNKQRBN QRNBBKRN RKNBBQNR RKNBBNQR RNNBBQKR BQRKNBNR RQNNBBKR BQRKNBNR RNBBNQKR RKBRNQNB NNBQRBKR RNQNBBKR NNRKRBBQ NRNQBBKR NQNRBBKR NRQNBBKR RNNQBBKR NRNBBQKR NRKBRQBN BQNBRNKR BRNBKNQR BRQBNNKR RBNKQRBN QRNBBKRN RKNBBQNR QBNRBNKR BRN...