QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647451 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | RE | 0ms | 0kb | C++20 | 3.7kb | 2024-10-17 14:16:58 | 2024-10-17 14:16:58 |
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 = "NNRKRBB";
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: 0
Runtime Error
input:
GAME 1
output:
NNRKRBB