QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#875388 | #7179. Fischer's Chess Guessing Game | shinonome_ena# | WA | 7ms | 11656kb | C++23 | 2.0kb | 2025-01-29 17:28:00 | 2025-01-29 17:28:01 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define MAX 505050
#define INF 1e18
vector<int> lst[960];
int N = 960;
int mp[1010][1010];
int adj[MAX][9];
int cr[MAX];
int ans[MAX];
string S = "KQRBN";
int make_tree(int loc, vector<int>& lst, int dep = 0) {
if (dep >= 6) return -1;
if (lst.size() == 1) {
ans[loc] = lst[0];
return loc;
}
ans[loc] = -1;
int i, c;
for (auto c : lst) {
vector<int> ch[9];
for (i = 0; i < 9; i++) ch[i] = vector<int>();
for (auto v : lst) ch[mp[c][v]].push_back(v);
int v = loc + 1;
int chk = 1;
for (i = 0; i < 9; i++) if (ch[i].size()) {
int res = make_tree(v, ch[i], dep + 1);
if (!~res) {
chk = 0;
break;
}
adj[loc][i] = v;
v = res + 1;
}
if (!chk) continue;
cr[loc] = c;
return v;
}
return -1;
}
void query(int loc) {
if (~ans[loc]) {
for (auto v : lst[ans[loc]]) cout << S[v];
cout << endl;
return;
}
for (auto v : lst[cr[loc]]) cout << S[v];
cout << endl;
int x;
cin >> x;
if (x == 8) return;
query(adj[loc][x]);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
vector<int> v = { 0, 1, 2, 2, 3, 3, 4, 4 };
int i, j, k;
int cnt = 0;
while (1) {
int k, r1, r2, b1, b2;
k = r1 = r2 = b1 = b2 = -1;
for (i = 0; i < 8; i++) {
if (v[i] == 0) k = i;
if (v[i] == 2) r2 = r1, r1 = i;
if (v[i] == 3) b2 = b1, b1 = i;
}
if (((b1 ^ b2) & 1) && r2 < k && k < r1) lst[cnt++] = v;
if (!next_permutation(v.begin(), v.end())) break;
}
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < 8; k++) mp[i][j] += lst[i][k] == lst[j][k];
}
}
vector<int> bum;
for (i = 0; i < N; i++) bum.push_back(i);
int M = make_tree(1, bum);
while (1) {
string s;
cin >> s;
if (s[0] == 'G') {
int a;
cin >> a;
query(1);
}
else break;
}
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 11656kb
input:
GAME 1 3 1 3 3 8 END
output:
QRKRBBNN QRKBNNBR QBRNBKRN QNRKBRNB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 11652kb
input:
GAME 1 3 1 3 3 8 GAME 2 2 1 3 4 8 GAME 3 2 1 2 4 8 GAME 4 1 3 2 2 8 GAME 5 1 3 1 4 4 8 GAME 6
output:
QRKRBBNN QRKBNNBR QBRNBKRN QNRKBRNB RKRBBQNN QRKRBBNN QRBKNNRB QNRBKRBN RKBBQRNN RKRBBNQN QRKRBBNN QRBKNNRB QNRBKRBN RKNBBQRN RKRBBNNQ QRKRBBNN QBRKNNBR QNBBRNKR BQRKRNNB RKRBQNBN QRKRBBNN QBRKNNBR QNBBRNKR RKNQNBBR RKQRNNBB RKRBNQBN
result:
wrong answer (i) illegal position "" (game 6, guess 1) (test case 6)