QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647474 | #7179. Fischer's Chess Guessing Game | no_RED_no_DEAD | TL | 0ms | 0kb | C++20 | 2.6kb | 2024-10-17 14:21:43 | 2024-10-17 14:21:44 |
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;
}
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;
vector<string> cv = v;
for (int i = 1;; i ++) {
assert(i <= 6);
string chs; ld cur = 1e18;
if (i == 1) chs = "NNRKRBB";
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: 0
Time Limit Exceeded
input:
GAME 1
output:
NNRKRBB