QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647443 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | RE | 205ms | 3848kb | C++20 | 3.7kb | 2024-10-17 14:13:49 | 2024-10-17 14:13:50 |
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);
}
map<string, ll> m;
void doTest(ll testID) {
backtrack(1, 0, 0, 0, 0, 0);
for (auto x: s) v.push_back(x);
ll cc = 0;
ll test = 0;
ll ok = 0;
while (true) {
string s; ll num; cin >> s; if (s == "END") return; cin >> num;
m.clear();
// /*#TEST*/ string real = v[cc]; cc++; ok ++; if (cc == v.size()) break;
// cout << "Real: " << real << endl;
vector<string> cv = v;
for (int i = 1;; i ++) {
/*#TEST*/ if (i == 7) {
// cout << real << endl;
// ok --; break;
}
assert(i <= 6);
const string fuck[] = {"NRNQBBKR", "NRBBNQKR", "NRBQNBKR", "NRNBBQKR"};
string chs; ld cur = 1e18;
if (i == 1) chs = v[rand(0, v.size() - 1)];
else {
// m["NRBBNQKR"] ++; m["NRBQNBKR"] ++; m["NRNBBQKR"] ++;
for (auto x: cv) {
if (m.count(x)) continue; 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 << cur << endl;
}
// if (i == 1) {cout << chs << endl; return;}
cout << chs << endl;
m[chs] ++;
ll req;
cin >> req;
// /*#TEST*/ req = get(real, chs);
if (req == 8) break;
vector<string> nv;
for (auto x: cv)
if (get(x, chs) == req)
nv.push_back(x);
cv = nv;
// cout << cv.size() << endl;
}
// /*#TEST*/ test ++; cout << "Accept test: " << test << endl;
}
// cout << "Total: " << ok << endl;
}
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: 1ms
memory: 3740kb
input:
GAME 1 0 5 4 4 8 END
output:
BRKNRNQB RKBBNQRN RKNBNQBR RKBBNRNQ RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 205ms
memory: 3744kb
input:
GAME 1 2 2 1 0 3 8 GAME 2 1 1 1 1 8 GAME 3 1 2 1 3 2 8 GAME 4 0 5 5 8 GAME 5 1 2 2 0 0 8 GAME 6 2 3 1 3 1 8 GAME 7 5 5 5 8 GAME 8 5 4 2 5 8 GAME 9 2 3 2 2 8 GAME 10 2 3 0 8 GAME 11 0 1 4 3 8 GAME 12 2 0 5 8 GAME 13 1 3 4 3 3 8 GAME 14 2 1 1 4 2 8 GAME 15 0 4 4 2 8 GAME 16 2 1 3 3 2 8 GAME 17 6 5 5 8...
output:
BRQBNKNR RBBNNQKR NNQRBBKR NRBKNRQB RKNBQNBR RKRBBQNN RBNNKRBQ BRNBNQKR NRKRBBNQ QBBRNKRN RKRBBNQN QRBBNKRN RKQNNBBR QNNRBBKR RBQKBRNN RBKRQNBN RKRBBNNQ NRBKNQRB RNKBQRBN RBKRQNBN RKRBQNBN RNKQBBNR BNRNKQRB BBRKNNQR BBNRKRNQ NRQKBNRB RKRBNQBN RKNQBBRN RQKNNBBR NRBQNBKR RBQKNRBN RBQNBKNR RKRBNNBQ RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 201ms
memory: 3848kb
input:
GAME 1 1 5 2 4 8 GAME 2 1 2 4 4 8 GAME 3 2 3 2 1 3 8 GAME 4 2 4 3 4 8 GAME 5 1 5 4 8 GAME 6 1 2 1 4 2 8 GAME 7 2 2 0 2 8 GAME 8 0 2 8 GAME 9 0 3 3 4 2 8 GAME 10 3 3 3 1 8 GAME 11 1 3 1 1 2 8 GAME 12 0 3 2 6 8 GAME 13 1 3 3 2 8 GAME 14 2 2 3 8 GAME 15 1 3 0 8 GAME 16 4 4 4 5 8 GAME 17 0 3 0 6 8 GAME ...
output:
NRKQRNBB RBQNBNKR BBRNQNKR RBQKBNRN RKQBBNNR NQRKBBRN RNBNQBKR RKNBQRBN RKNNBRQB RKNBBQNR QRKNBNRB RBQNKNBR NRBNKBQR RBBNQKRN NBRQBNKR RKNBBNQR BRNBNKRQ RBNKNQBR NBRQNKBR RBKRNNBQ RKQBNNBR NRQNBBKR RQKBNNBR RQBBKNNR RKNBQNBR NBBRKQRN NRKBBNQR QRNNBKRB RBNKQNBR BBNQRNKR RKNBNQBR BBRNQNKR BRNBKQNR BBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: -100
Runtime Error
input:
GAME 1 3 2 1 1 8 GAME 2 1 2 4 2 4 8 GAME 3 1 0 0 4 8 GAME 4 1 3 3 2 8 GAME 5 0 3 3 8 GAME 6 0 4 1 5 8 GAME 7 0 1 2 2 8 GAME 8 1 1 2 2 8 GAME 9 0 3 2 0 8 GAME 10 4 4 2 5 8 GAME 11 3 4 3 2 6 8 GAME 12 2 0 2 4 6 8 GAME 13 2 3 1 2 2 8 GAME 14 2 3 1 2 8 GAME 15 1 2 1 2 2 8 GAME 16 3 1 4 8 GAME 17 2 1 1 0...
output:
QRKNRNBB NRKBNQBR BRNNKQRB QNRKNRBB QRKRBBNN RBBNNKQR RKQBBNRN NRKNBQRB NRBQKNRB BRKNQBRN NRKRBBQN QBRKBNRN RKQBNNBR BNNQRKRB NBBRKRNQ NRKRBBNQ RNBBQKNR BRQKNRNB NRKNQRBB NNRKBRQB QRKRBNNB RBQNKRBN NNRBBQKR NRNBBKRQ NRKRBQNB RNBKQBNR NRKQNRBB NBRQKRBN NRKNBQRB NRKRBNQB BNRNKRQB NRBBQKNR RBKRBNNQ RBN...