QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196943 | #7179. Fischer's Chess Guessing Game | ucup-team1430 | AC ✓ | 702ms | 4180kb | C++20 | 2.7kb | 2023-10-02 04:47:52 | 2023-10-02 04:47:53 |
Judging History
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 --) {
if (p.size() == 1) {
print(p[0]); cout.flush();
int x; cin >> x; assert(x == 8);
return;
}
int id = choose(p);
print(p_ini[id]);
cout.flush();
int x; cin >> x;
if (x == 8) { return; }
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: 100
Accepted
time: 5ms
memory: 3820kb
input:
GAME 1 3 1 4 1 1 8 END
output:
RQKNBBRN NRNKBBQR RKBRNQNB RQNKNBBR RQNNKRBB RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: 0
Accepted
time: 669ms
memory: 3920kb
input:
GAME 1 3 1 4 1 1 8 GAME 2 3 2 3 1 1 8 GAME 3 2 2 2 3 1 8 GAME 4 2 0 2 3 2 8 GAME 5 2 0 1 2 2 8 GAME 6 1 3 5 2 8 GAME 7 4 3 5 1 8 GAME 8 5 5 6 8 GAME 9 4 4 4 3 8 GAME 10 2 3 2 2 2 8 GAME 11 3 1 5 3 8 GAME 12 3 2 4 3 8 GAME 13 3 1 3 4 8 GAME 14 4 3 5 2 8 GAME 15 3 1 3 3 3 8 GAME 16 1 4 3 3 8 GAME 17 2...
output:
RQKNBBRN NRNKBBQR RKBRNQNB RQNKNBBR RQNNKRBB RKRBBQNN RQKNBBRN NRNKBBQR RNQKBNRB RQNNKBBR RQNNKRBB RKRBBNQN RQKNBBRN NRKQBBNR RNBQKBNR RQNKBRNB RQNNKRBB RKRBBNNQ RQKNBBRN NRKQBBNR BNRNQKRB RQKNRNBB RQNNKRBB RKRBQNBN RQKNBBRN NRKQBBNR BNRNQKRB RNNKQRBB RQNNKRBB RKRBNQBN RQKNBBRN RQBKNNRB RKNBNQBR RQN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 631ms
memory: 3880kb
input:
GAME 1 2 3 3 2 1 8 GAME 2 2 3 4 4 8 GAME 3 2 2 2 3 2 8 GAME 4 1 3 6 2 8 GAME 5 1 2 5 4 8 GAME 6 1 2 6 2 8 GAME 7 4 5 4 8 GAME 8 3 4 6 2 8 GAME 9 4 4 3 4 8 GAME 10 3 2 2 3 5 8 GAME 11 2 3 3 6 8 GAME 12 3 3 2 6 8 GAME 13 4 2 3 1 8 GAME 14 4 1 3 2 8 GAME 15 3 1 3 1 1 8 GAME 16 3 0 6 2 8 GAME 17 3 0 4 2...
output:
RQKNBBRN NRKQBBNR RBNNBKQR RNNQKBBR RQNNKRBB RKQBBNNR RQKNBBRN NRKQBBNR RBNNBKQR RNKBBRNQ RKNBBQNR RQKNBBRN NRKQBBNR RNBQKBNR RQNKBRNB RQNNKRBB RKNBBNQR RQKNBBRN RQBKNNRB RKNBNQBR RQNNKRBB RKQBNNBR RQKNBBRN RQBKNNRB RQNBNKBR RQNKRNBB RKNBQNBR RQKNBBRN RQBKNNRB RQNBNKBR RNNQBKRB RKNBNQBR RQKNBBRN RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 659ms
memory: 4028kb
input:
GAME 1 4 2 1 2 8 GAME 2 4 1 2 0 8 GAME 3 3 4 3 0 8 GAME 4 2 4 1 0 8 GAME 5 2 5 0 2 8 GAME 6 2 4 0 1 8 GAME 7 3 2 0 8 GAME 8 3 3 0 1 1 8 GAME 9 2 4 1 2 8 GAME 10 1 3 2 3 2 8 GAME 11 1 2 1 2 3 8 GAME 12 1 2 2 1 2 8 GAME 13 2 3 0 2 0 8 GAME 14 2 2 0 4 0 8 GAME 15 1 1 0 0 8 GAME 16 3 2 0 4 8 GAME 17 4 2...
output:
RQKNBBRN RQBNKBNR RNNKBQRB RQNKRBBN QRKRBBNN RQKNBBRN RQBNKBNR RQNBBKRN RQBNKNRB NRKRBBQN RQKNBBRN NRNKBBQR RQNKBBNR RQNKRNBB NRKRBBNQ RQKNBBRN NRKQBBNR RQBNKBNR RQNNKBBR QRKRBNNB RQKNBBRN NRKQBBNR RQNNKBBR RQNNBKRB NRKRBQNB RQKNBBRN NRKQBBNR RQBNKBNR RQNNKRBB NRKRBNQB RQKNBBRN NRNKBBQR RNQKBNRB QRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 673ms
memory: 4000kb
input:
GAME 1 4 3 3 8 GAME 2 3 2 4 1 2 8 GAME 3 2 1 1 3 3 8 GAME 4 2 0 1 5 5 8 GAME 5 1 4 1 6 8 GAME 6 1 3 4 6 5 8 GAME 7 2 1 4 1 2 8 GAME 8 2 0 0 6 8 GAME 9 1 4 5 3 8 GAME 10 3 2 4 2 2 8 GAME 11 3 4 4 2 8 GAME 12 2 2 2 6 8 GAME 13 2 0 0 4 3 8 GAME 14 2 0 1 6 4 8 GAME 15 1 3 4 4 8 GAME 16 2 1 3 5 8 GAME 17...
output:
RQKNBBRN RQBNKBNR RKBRQBNN RQNKRBBN RQKNBBRN NRNKBBQR RNQKBNRB RQNBBNKR RQNNKRBB RNQKRBBN RQKNBBRN NRKQBBNR RBBQKNNR RQKRNBBN RQNNKRBB RNNKRBBQ RQKNBBRN NRKQBBNR BNRNQKRB RNNKQRBB RQNNKRBB RQNKRNBB RQKNBBRN RQBKNNRB RKBRNBNQ RNQKNRBB RNQKRNBB RQKNBBRN RQBKNNRB RKNBNQBR RQNKRNBB RQNKRBBN RNNKRQBB RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 689ms
memory: 4152kb
input:
GAME 1 3 3 1 1 3 8 GAME 2 3 4 2 0 8 GAME 3 2 3 0 0 0 8 GAME 4 1 6 8 GAME 5 1 5 1 2 8 GAME 6 1 5 2 1 8 GAME 7 4 1 4 1 8 GAME 8 4 1 3 3 8 GAME 9 3 6 1 8 GAME 10 2 2 0 2 2 8 GAME 11 2 3 1 2 1 8 GAME 12 2 3 2 1 8 GAME 13 1 2 2 5 8 GAME 14 1 1 1 6 8 GAME 15 1 2 3 3 1 8 GAME 16 1 3 2 1 2 8 GAME 17 1 2 1 1...
output:
RQKNBBRN NRNKBBQR RNNQBKRB RQNNKBBR RQBNNKRB QRBKNBRN RQKNBBRN NRNKBBQR RQNKBBNR RQNNKRBB NRBKQBRN RQKNBBRN NRKQBBNR RBNNBKQR RQNBKRBN RQNNKRBB NRBKNBRQ RQKNBBRN RQBKNNRB QRBKNNRB RQKNBBRN RQBKNNRB RQBNNBKR RQNKNRBB NRBKQNRB RQKNBBRN RQBKNNRB RQBNNBKR RQNNKRBB NRBKNQRB RQKNBBRN RQBNKBNR RQNBBKRN RNQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 685ms
memory: 4112kb
input:
GAME 1 2 2 5 3 8 GAME 2 3 1 2 4 8 GAME 3 2 1 5 2 8 GAME 4 3 0 2 5 8 GAME 5 2 1 4 3 5 8 GAME 6 2 0 1 4 6 8 GAME 7 3 0 1 3 4 8 GAME 8 2 0 1 3 8 GAME 9 1 2 2 3 3 8 GAME 10 3 0 2 6 8 GAME 11 1 3 1 4 4 8 GAME 12 2 0 3 6 8 GAME 13 3 1 1 0 8 GAME 14 2 0 1 4 4 8 GAME 15 1 1 0 6 8 GAME 16 3 1 2 8 GAME 17 2 0...
output:
RQKNBBRN NRKQBBNR RNBQKBNR RBQNKNBR RBBQKRNN RQKNBBRN NRNKBBQR RKBRNQNB RQNNKRBB RBBNKRQN RQKNBBRN NRKQBBNR RBBQKNNR RQNNBBKR RBBNKRNQ RQKNBBRN NRNKBBQR RNKRQNBB RQNNKRBB RBQNKRBN RQKNBBRN NRKQBBNR RBBQKNNR RQNBNKBR RQNNKRBB RBNQKRBN RQKNBBRN NRKQBBNR BNRNQKRB RNNKQRBB RQNNKRBB RBNNKRBQ RQKNBBRN NRN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 702ms
memory: 3892kb
input:
GAME 1 0 2 2 4 8 GAME 2 0 3 2 2 2 8 GAME 3 0 1 1 3 8 GAME 4 2 3 3 5 8 GAME 5 2 4 4 3 8 GAME 6 1 0 2 6 8 GAME 7 1 0 4 0 2 8 GAME 8 2 0 3 3 3 8 GAME 9 1 0 4 0 3 8 GAME 10 2 1 2 2 3 8 GAME 11 1 0 3 4 2 8 GAME 12 0 1 3 0 8 GAME 13 2 1 2 3 3 8 GAME 14 0 1 4 1 8 GAME 15 1 1 0 4 4 8 GAME 16 2 0 2 2 4 8 GAM...
output:
RQKNBBRN BBQRNNKR RNBBNKQR NRNBBQKR QRNBKNBR RQKNBBRN BBQRNNKR RNNBBKQR RQNKRNBB RQNNKRBB NRQBKNBR RQKNBBRN BBQRNNKR BRQKNRNB RQNNKRBB NRNBKQBR RQKNBBRN NRKQBBNR RBNNBKQR RNNQKBBR QRNNKBBR RQKNBBRN NRKQBBNR RQBNKBNR RQNNKRBB NRQNKBBR RQKNBBRN RQBKNNRB RBQNKRBN NNRQKBBR NRNQKBBR RQKNBBRN RQBKNNRB RBQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 675ms
memory: 4112kb
input:
GAME 1 0 4 2 2 8 GAME 2 0 3 1 2 8 GAME 3 0 4 1 1 8 GAME 4 0 4 4 3 8 GAME 5 0 5 3 1 8 GAME 6 0 3 2 2 3 8 GAME 7 1 1 3 4 2 8 GAME 8 2 4 6 2 8 GAME 9 1 1 4 3 3 8 GAME 10 1 0 2 5 8 GAME 11 2 3 2 3 4 8 GAME 12 1 0 3 3 8 GAME 13 3 0 1 2 3 8 GAME 14 4 3 4 2 8 GAME 15 3 0 1 3 2 8 GAME 16 5 3 5 8 GAME 17 4 1...
output:
RQKNBBRN BBQRNNKR QRNBNKBR RBNKNQBR QBBRKNNR RQKNBBRN BBQRNNKR RNNBBKQR RBKNQNBR NBBRKQNR RQKNBBRN BBQRNNKR QRNBNKBR RKRQBNNB NBBRKNQR RQKNBBRN BBQRNNKR QRNBNKBR RQNBKRBN QBNRKNBR RQKNBBRN BBQRNNKR RNQKNBBR RQNKNRBB NBQRKNBR RQKNBBRN BBQRNNKR RNNBBKQR RQNKRNBB RQNNKRBB NBNRKQBR RQKNBBRN RQBKNNRB NBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 678ms
memory: 3952kb
input:
GAME 1 0 4 3 3 8 GAME 2 1 0 2 2 1 8 GAME 3 1 1 3 2 2 8 GAME 4 1 2 5 1 8 GAME 5 0 2 4 2 8 GAME 6 0 3 5 0 8 GAME 7 2 3 5 3 8 GAME 8 1 0 1 3 0 8 GAME 9 2 3 6 8 GAME 10 1 1 3 2 3 8 GAME 11 0 3 2 1 1 8 GAME 12 1 0 3 1 2 8 GAME 13 1 0 0 5 0 8 GAME 14 2 4 3 1 8 GAME 15 1 0 0 4 0 8 GAME 16 0 2 5 1 8 GAME 17...
output:
RQKNBBRN BBQRNNKR QRNBNKBR RBBNNKRQ BBRQNKNR RQKNBBRN RQBKNNRB RBQNKRBN NNRQKBBR RQNNKRBB BBRNQKNR RQKNBBRN RQBKNNRB NBBRNQKR RKBQNBNR RQNNKBBR BBRNNKQR RQKNBBRN RQBKNNRB RQNBNKBR RQNKRNBB BQRBNKNR RQKNBBRN BBQRNNKR RNBBNKQR NNBQRBKR BNRBQKNR RQKNBBRN BBQRNNKR RNNBBKQR RQNNKRBB BNRBNKQR RQKNBBRN NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 667ms
memory: 4180kb
input:
GAME 1 3 3 3 4 4 8 GAME 2 2 2 3 2 1 8 GAME 3 2 2 3 1 3 8 GAME 4 5 4 6 8 GAME 5 4 4 3 3 8 GAME 6 3 4 5 8 GAME 7 0 6 5 3 8 GAME 8 0 4 4 2 8 GAME 9 0 4 5 3 8 GAME 10 2 3 2 3 1 8 GAME 11 1 1 3 4 4 8 GAME 12 2 3 3 3 2 8 GAME 13 0 4 5 2 8 GAME 14 0 3 2 1 0 8 GAME 15 0 3 2 0 0 8 GAME 16 2 3 2 4 1 8 GAME 17...
output:
RQKNBBRN NRNKBBQR RNNQBKRB RQNNKBBR RQNKRNBB RQNBBNKR RQKNBBRN NRKQBBNR RNBQKBNR RQKRNNBB RQNNKRBB RNQBBNKR RQKNBBRN NRKQBBNR RNBQKBNR RQKRNNBB RQNNBKRB RNNBBQKR RQKNBBRN RKNNBRQB RQNNKBBR RQNNBBKR RQKNBBRN RQBNKBNR RQKNBRNB RNNKBRQB RNQNBBKR RQKNBBRN NRNKBBQR RQNKBBNR RNNQBBKR RQKNBBRN BBQRNNKR RQB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed