QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291850 | #7179. Fischer's Chess Guessing Game | OAleksa | WA | 80ms | 3572kb | C++14 | 2.4kb | 2023-12-27 09:48:15 | 2023-12-27 09:48:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 960;
vector<int> g(N);
vector<char> sv = {'K', 'Q', 'N', 'N', 'B', 'B', 'R', 'R'};
vector<string> perm;
int good(vector<char> ord) {
int x = -1, y = -1, z = -1, b = -1, a = -1;
for (int i = 0;i < 8;i++) {
if (ord[i] == 'K')
z = i;
else if (ord[i] == 'B') {
if (x == -1)
x = i;
else
y = i;
}
else if (ord[i] == 'R') {
if (a == -1)
a = i;
else
b = i;
}
}
return z < b && z > a && x % 2 != y % 2;
};
int diff(string a, string b) {
int r = 0;
for (int i = 0;i < 8;i++)
r += (a[i] == b[i]);
return r;
};
string ans;
void resi(int r) {
int x = 0;
for (int i = 0;i < N;i++) {
if (diff(perm[i], ans) != r) {
g[i] = false;
x++;
}
}
int mn = 1e9;
for (int i = 0;i < N;i++) {
if (!g[i])
continue;
int mx = 0;
vector<int> cnt(10);
for (int j = 0;j < N;j++) {
if (!g[j])
continue;
mx = max(mx, ++cnt[diff(perm[i], perm[j])]);
}
if (mx < mn) {
mn = mx;
ans = perm[i];
}
}
//cout << mn << " " << x << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
//freopen("newbarn.in", "r", stdin);
//freopen(newbarn.out", "w", stdout);
int tt = 1;
//cin >> tt;
while (tt--) {
vector<int> order(8);
iota(order.begin(), order.end(), 0);
map<string, int> bio;
while (next_permutation(order.begin(), order.end())) {
vector<char> t;
for (int i = 0;i < 8;i++)
t.push_back(sv[order[i]]);
if (good(t)) {
string s;
for (auto x : t)
s += x;
if (bio[s])
continue;
bio[s] = 1;
perm.push_back(s);
}
}
int mx = 1e9;
string ans1;
for (int i = 0;i < 960;i++) {
vector<int> cnt(10);
int l = 0;
for (int j = 0;j < 960;j++)
l = max(l, ++cnt[diff(perm[i], perm[j])]);
if (l < mx) {
ans1 = perm[i];
mx = l;
}
}
ans1 = "NRBBNKQR";
while (true) {
string s;
cin >> s;
if (s == "GAME") {
ans = ans1;
for (int i = 0;i < N;i++)
g[i] = 1;
cin >> s;
int c = 0;
while (true) {
cout << ans << endl;
c++;
int r;
cin >> r;
if (r == 8 || c == 6)
break;
resi(r);
}
}
else
break;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 17ms
memory: 3572kb
input:
GAME 1 1 2 2 1 2 8 END
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN QNRNBKRB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 80ms
memory: 3572kb
input:
GAME 1 1 2 2 1 2 8 GAME 2 2 1 4 1 8 GAME 3 1 2 2 0 8 GAME 4 1 2 1 3 3 8 GAME 5 2 1 3 1 0 8 GAME 6 2 1 2 4 1 8 GAME 7 0 2 3 6 8 GAME 8 1 2 1 1 8 GAME 9 0 3 1 2 8 GAME 10 0 3 3 3 8 GAME 11 0 5 3 3 8 GAME 12 1 1 2 3 4 8 GAME 13 1 2 2 3 4 8 GAME 14 0 4 3 8 GAME 15 1 2 1 2 0 8 GAME 16 1 1 1 1 8 GAME 17 0...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN QNRNBKRB RKRBBQNN NRBBNKQR RNBNQBKR QNRBBKRN QRNNBKRB RKRBBNQN NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RKRBBNNQ NRBBNKQR BNRKQBNR RNBQKRNB NQRKRNBB QBRKNRBN RKRBQNBN NRBBNKQR RNBNQBKR QNRBBKRN NNRKBRQB QBNRBKNR RKRBNQBN NRBBNKQR RNBNQBKR QNRBBKRN QBRKNNBR NBRKBQNR RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: -100
Wrong Answer
time: 17ms
memory: 3560kb
input:
GAME 1 2 2 2 3 3 3
output:
NRBBNKQR RNBNQBKR NBRKQNBR BQNBRNKR BNRBKQNR BBQNRKNR
result:
wrong answer (i) too many guesses in game 1, pos = `\x16B\x1c