QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196933 | #7179. Fischer's Chess Guessing Game | ucup-team1430 | TL | 0ms | 0kb | C++20 | 2.6kb | 2023-10-02 04:43:06 | 2023-10-02 04:43:07 |
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define sws cin.tie(0)->sync_with_stdio(false);
const int N = 0;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
bool is_valid(vector<char> s) {
int n = s.size();
bool ok = true;
int bishop = -1, rook = -1;
for (int i=0;i<n;i++) {
auto c = s[i];
if (c == 'B') {
if (bishop == -1) bishop = i;
else ok &= ((i - bishop) % 2 == 1);
} else if (c == 'R') {
if (rook == -1) rook = i;
else rook = -1;
} else if (c == 'K') {
ok &= (rook != -1);
}
}
return ok;
}
auto dist = [](vector<char> &a, vector<char> &b) {
int qnt = 0;
int n = a.size();
for (int i=0;i<n;i++) {
if (a[i] != b[i]) qnt ++;
}
return qnt;
};
void solve() {
vector<char> pos = {'K', 'Q', 'R', 'R', 'N', 'N', 'B', 'B'};
sort(pos.begin(), pos.end());
vector<vector<char>> p_ini;
do {
p_ini.push_back(pos);
} while (next_permutation(pos.begin(), pos.end()));
vector<vector<char>> p;
for (auto pi: p_ini) if (is_valid(pi)) p.push_back(pi);
p_ini = p;
auto print = [&](vector<char> &x) {
for (auto c: x) cout << c;
cout << endl;
};
auto choose = [&](vector<vector<char>> &p) {
int n = p_ini.size();
int m = p.size();
int id = 0, mx = INF;
for (int i=0;i<n;i++) {
vector<int> dists(10, 0);
for (int j=0;j<m;j++) {
int d = dist(p_ini[i], p[j]);
dists[d] ++;
}
int dmax = 0;
for (auto d: dists) dmax = max(dmax, d);
if (dmax <= mx) {
id = i; mx = dmax;
}
}
return id;
};
int it = 6;
while (it --) {
int id = choose(p);
if (p.size() == 1) {
print(p[0]);
int x; cin >> x; assert(x == 8);
return;
}
print(p_ini[id]);
cout.flush();
int x; cin >> x;
vector<vector<char>> p2;
for (auto pi: p) {
if (dist(p_ini[id], pi) == 8 - x) {
p2.push_back(pi);
}
}
swap(p, p2);
}
}
int main() {
#ifndef LOCAL
sws;
#endif
string s; int t;
while (cin >> s >> t) {
// if (s == "END") return 0;
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
GAME 1 3 1 4 1 1
output:
RQKNBBRN NRNKBBQR RKBRNQNB RQNKNBBR RQNNKRBB