QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647445 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | RE | 174ms | 4032kb | C++20 | 3.7kb | 2024-10-17 14:15:24 | 2024-10-17 14:15:25 |
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 = fuck[rand(0, 3)];
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: 4ms
memory: 3728kb
input:
GAME 1 2 2 1 4 8 END
output:
NRBBNQKR RBBNQKNR RQNKNBBR RKBBRNQN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 174ms
memory: 4032kb
input:
GAME 1 3 2 3 1 8 GAME 2 1 4 5 4 8 GAME 3 1 2 0 2 3 8 GAME 4 0 1 4 1 8 GAME 5 2 1 1 0 4 8 GAME 6 1 5 4 4 8 GAME 7 3 2 4 3 8 GAME 8 1 2 1 3 2 8 GAME 9 2 1 4 5 3 8 GAME 10 0 6 4 8 GAME 11 1 3 1 1 3 8 GAME 12 1 3 4 5 8 GAME 13 1 4 2 8 GAME 14 0 2 2 3 2 8 GAME 15 2 0 2 0 8 GAME 16 0 2 5 4 8 GAME 17 0 3 2...
output:
NRNBBQKR RNBBQNKR RBNQBKNR NRBQKBNR RKRBBQNN NRNQBBKR RKQBNNBR RKQBBRNN RKNBQRBN RKRBBNQN NRBBNQKR RKNNQBBR BRNNKRQB NNRKRBBQ RBKRNNBQ RKRBBNNQ NRBQNBKR BNRNKRQB RKQBBRNN RBNKBRNQ RKRBQNBN NRNBBQKR RBQNBKNR NRKNQRBB NNBRKBQR RKNBRNBQ RKRBNQBN NRBQNBKR RKNBQNBR RKQBBNNR RKBBQNRN RKRBNNBQ NRNQBBKR RNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: -100
Runtime Error
input:
GAME 1 2 3 2 4 3 8 GAME 2 3 2 3 0 8 GAME 3 4 1 3 2 8 GAME 4 1 8 GAME 5 2 3 4 2 3 8 GAME 6 2 1 6 8 GAME 7 2 2 2 3 8 GAME 8 3 4 5 2 8 GAME 9 1 6 4 8 GAME 10 2 3 1 8 GAME 11 4 5 3 8 GAME 12 1 8 GAME 13 0 0 3 8 GAME 14 0 2 4 4 8 GAME 15 0 0 2 8 GAME 16 0 1 4 1 8 GAME 17 0 0 3 3 8 GAME 18 0 0 2 4 8 GAME ...
output:
NRBBNQKR RBBNQKNR BBNRQNKR RNQNBBKR BRQNKBNR RKQBBNNR NRNQBBKR RNBNQBKR RQNKBBRN NRBKRBQN RKNBBQNR NRNBBQKR NRKBRQBN NBRQBNKR BBNRNQKR RKNBBNQR NRNQBBKR RKQBNNBR NRBBNQKR RBBNQKNR BBNRQNKR NBNRBKQR BRNKQBNR RKNBQNBR NRBQNBKR QBBRKNNR RNKBNQBR RKNBNQBR NRBQNBKR QBBRKNNR RBBNNKRQ RQBKRBNN RKQNBBNR NRB...