QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176262 | #7179. Fischer's Chess Guessing Game | HaccerKat | AC ✓ | 1663ms | 4064kb | C++20 | 6.3kb | 2023-09-11 13:59:35 | 2023-09-11 13:59:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
return t.size();
}
template<typename T, size_t N>
int SIZE(T (&t)[N]){
return N;
}
string to_string(char t){
return "'" + string({t}) + "'";
}
string to_string(bool t){
return t ? "true" : "false";
}
string to_string(const string &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += t[i];
}
return '"' + ret + '"';
}
string to_string(const char* t){
string ret(t);
return to_string(ret);
}
template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
string ret = "";
for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
ret += t[i] + '0';
}
return to_string(ret);
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);
template<typename T, typename S>
string to_string(const pair<T, S> &t){
return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}
template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
string ret = "[";
x1 = min(x1, SIZE(t));
auto e = begin(t);
advance(e,x1);
for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
ret += to_string(*e, C...) + (i != _i ? ", " : "");
e = next(e);
}
return ret + "]";
}
template<int Index, typename... Ts>
struct print_tuple{
string operator() (const tuple<Ts...>& t) {
string ret = print_tuple<Index - 1, Ts...>{}(t);
ret += (Index ? ", " : "");
return ret + to_string(get<Index>(t));
}
};
template<typename... Ts>
struct print_tuple<0, Ts...> {
string operator() (const tuple<Ts...>& t) {
return to_string(get<0>(t));
}
};
template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
const auto Size = tuple_size<tuple<Ts...>>::value;
return print_tuple<Size - 1, Ts...>{}(t);
}
void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
cout << to_string(H) << " | ";
dbgr(T...);
}
void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
cout << H << " ";
dbgs(T...);
}
/*
formatted functions:
*/
/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)
/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int X = 960;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
char c[5] = {'K', 'R', 'B', 'N', 'Q'};
int idx = 0;
vector<vector<int>> positions(X);
void dfs(vector<int> a, int p = 0) {
if (p == 5) {
positions[idx++] = a;
return;
}
if (p == 0 || p == 4) {
for (int i = 0; i < 8; i++) {
if (a[i] != -1 || (p == 0 && (i == 0 || i == 7))) continue;
vector<int> b = a;
b[i] = p;
dfs(b, p + 1);
}
}
else {
int kp = -1;
for (int i = 0; i < 8; i++) {
if (a[i] == 0) kp = i;
}
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 8; j++) {
if (a[i] != -1 || a[j] != -1) continue;
vector<int> b = a;
bool ok = 0;
if (p == 1 && i < kp && j > kp) b[i] = b[j] = p, ok = 1;
if (p == 2 && (i & 1) != (j & 1)) b[i] = b[j] = p, ok = 1;
if (p == 3) b[i] = b[j] = p, ok = 1;
if (ok) dfs(b, p + 1);
}
}
}
}
int query(vector<int> a) {
for (int i = 0; i < 8; i++) {
cout << c[a[i]];
}
cout << endl;
int x;
cin >> x;
return x;
}
int n, m, k, qq;
void solve() {
vector<vector<int>> cand = positions;
vector<int> test = {1, 3, 2, 4, 0, 2, 3, 1};
while (true) {
if (cand.size() == 1) {
query(cand[0]);
break;
}
vector<int> best;
int val = inf;
for (auto a : positions) {
vector<int> cnt(9);
for (auto b : cand) {
int x = 0;
for (int i = 0; i < 8; i++) {
x += a[i] == b[i];
}
cnt[x]++;
}
int mx = 0;
for (int i = 0; i <= 8; i++) mx = max(mx, cnt[i]);
if (mx < val) val = mx, best = a;
}
vector<vector<int>> ncand;
int x = query(best);
if (x == 8) break;
for (auto a : cand) {
int y = 0;
for (int i = 0; i < 8; i++) {
y += best[i] == a[i];
}
if (x == y) ncand.push_back(a);
}
swap(cand, ncand);
}
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
dfs(vector<int>(8, -1));
string s;
int x;
while (true) {
cin >> s;
if (s == "END") break;
cin >> x;
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 32ms
memory: 3796kb
input:
GAME 1 4 3 5 6 8 END
output:
RQKBBNRN RQKNBRNB RKRNBBQN RKRBBNNQ RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: 0
Accepted
time: 1657ms
memory: 3780kb
input:
GAME 1 4 3 5 6 8 GAME 2 5 5 6 8 GAME 3 4 3 4 3 8 GAME 4 4 1 3 6 8 GAME 5 3 1 4 6 5 8 GAME 6 3 1 6 8 GAME 7 3 1 5 5 8 GAME 8 3 2 0 8 GAME 9 2 2 4 2 6 8 GAME 10 3 1 6 4 8 GAME 11 2 3 2 1 5 8 GAME 12 3 2 1 0 8 GAME 13 2 0 4 6 8 GAME 14 2 0 5 6 8 GAME 15 1 3 3 5 4 8 GAME 16 2 0 3 4 4 8 GAME 17 2 0 4 4 8...
output:
RQKBBNRN RQKNBRNB RKRNBBQN RKRBBNNQ RKRBBQNN RQKBBNRN RKNRBNQB RKNBBRQN RKRBBNQN RQKBBNRN RQKNBRNB RKRNBBQN RKBRNNQB RKRBBNNQ RQKBBNRN RQKNBRNB RKBRNNQB RKRNQBBN RKRBQNBN RQKBBNRN NRNBBKQR RKRBBNNQ RKRBBQNN RKRBBNQN RKRBNQBN RQKBBNRN NRNBBKQR RKRBBNNQ RKRBNNBQ RQKBBNRN NRNBBKQR RKRBBNNQ RKRBBNQN RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 1520ms
memory: 3856kb
input:
GAME 1 4 3 3 6 8 GAME 2 3 4 6 8 GAME 3 4 2 1 4 8 GAME 4 3 2 4 4 4 8 GAME 5 3 3 4 5 8 GAME 6 2 3 3 6 8 GAME 7 2 3 3 2 4 8 GAME 8 2 3 4 4 8 GAME 9 2 2 4 2 3 8 GAME 10 1 2 4 6 8 GAME 11 1 2 4 8 GAME 12 1 1 0 4 2 8 GAME 13 4 4 4 3 8 GAME 14 5 5 4 8 GAME 15 4 4 6 3 8 GAME 16 4 2 1 2 8 GAME 17 3 0 3 3 8 G...
output:
RQKBBNRN RQKNBRNB RKRNBBQN RKRBBNNQ RKQBBNNR RQKBBNRN NRNBBKQR RKNRBQNB RKNBBQNR RQKBBNRN RQKNBRNB NRQKBBRN RKRQBNNB RKNBBNQR RQKBBNRN NRNBBKQR NRKBQNBR RKRBBNNQ RKRBBNQN RKQBNNBR RQKBBNRN NRNBBKQR QRKBNNBR RKRNQNBB RKNBQNBR RQKBBNRN NRKBBQNR RBNKBNQR RKRBNQBN RKNBNQBR RQKBBNRN NRKBBQNR RBNKBNQR RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 1621ms
memory: 4008kb
input:
GAME 1 3 2 2 3 8 GAME 2 3 4 2 1 8 GAME 3 2 5 3 3 8 GAME 4 3 2 3 1 3 8 GAME 5 2 6 0 3 8 GAME 6 3 4 3 2 8 GAME 7 2 2 1 5 2 8 GAME 8 2 3 0 4 8 GAME 9 1 2 1 4 8 GAME 10 2 2 0 4 8 GAME 11 2 3 1 4 8 GAME 12 1 1 0 3 1 8 GAME 13 3 2 3 1 2 8 GAME 14 4 1 2 2 8 GAME 15 3 2 4 4 2 8 GAME 16 2 3 0 3 1 8 GAME 17 2...
output:
RQKBBNRN NRNBBKQR NRKBQNBR RKBQRBNN QRKRBBNN RQKBBNRN NRNBBKQR RKNRBQNB RKRBBNNQ NRKRBBQN RQKBBNRN NRKBBQNR RKBNRBNQ RKRBBNNQ NRKRBBNQ RQKBBNRN NRNBBKQR NRKBQNBR RKRBNNBQ RKRBBNNQ QRKRBNNB RQKBBNRN NRKBBQNR RKRBNNBQ RKRBBQNN NRKRBQNB RQKBBNRN NRNBBKQR RKNRBQNB RKRBBNNQ NRKRBNQB RQKBBNRN NRKBBQNR RNQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 1642ms
memory: 3752kb
input:
GAME 1 3 1 1 3 2 8 GAME 2 2 0 4 3 1 8 GAME 3 1 3 2 3 2 8 GAME 4 3 1 2 4 8 GAME 5 2 0 3 2 3 8 GAME 6 1 2 4 3 8 GAME 7 2 1 3 2 3 8 GAME 8 2 0 1 3 2 8 GAME 9 1 4 0 3 8 GAME 10 3 1 3 4 8 GAME 11 3 3 0 3 4 8 GAME 12 2 2 4 0 2 8 GAME 13 2 0 2 2 1 8 GAME 14 2 0 3 3 4 8 GAME 15 1 3 4 2 2 8 GAME 16 2 1 3 3 2...
output:
RQKBBNRN NRNBBKQR RKRBBNNQ RKRNNBBQ RKRBBNQN RQNKRBBN RQKBBNRN NRKBBQNR RKNNRBBQ RKRBNQBN RKRBBNNQ RNQKRBBN RQKBBNRN RNBBNKRQ RBBNKRNQ RKNRNQBB RKRBBNNQ RNNKRBBQ RQKBBNRN NRNBBKQR RKRBBNNQ RQKBNNBR RQNKRNBB RQKBBNRN NRKBBQNR RKNNRBBQ RKNRNBBQ RKRBNNBQ RNQKRNBB RQKBBNRN RNBBNKRQ RKNNQRBB RKNQNBBR RNN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 1646ms
memory: 3696kb
input:
GAME 1 2 1 4 5 1 8 GAME 2 2 2 2 0 0 8 GAME 3 1 4 3 2 8 GAME 4 2 1 6 2 8 GAME 5 2 2 1 2 0 8 GAME 6 1 3 1 5 0 8 GAME 7 3 3 2 1 1 8 GAME 8 3 3 1 1 8 GAME 9 2 3 3 0 2 8 GAME 10 3 3 3 0 8 GAME 11 3 3 2 3 8 GAME 12 2 4 0 1 8 GAME 13 0 4 4 2 8 GAME 14 0 2 3 1 8 GAME 15 0 3 0 3 8 GAME 16 0 3 0 5 8 GAME 17 0...
output:
RQKBBNRN NRKBBQNR NRBKQNRB QBBRNKRN RKRBBNQN QRBKNBRN RQKBBNRN NRKBBQNR RNQKBBNR QBRNKNBR RKRBBNNQ NRBKQBRN RQKBBNRN RNBBNKRQ NRQNBKRB RKRNBBNQ NRBKNBRQ RQKBBNRN NRKBBQNR NRBKQNRB RKRBNNBQ QRBKNNRB RQKBBNRN NRKBBQNR RNQKBBNR QRKNNRBB RKRBBQNN NRBKQNRB RQKBBNRN RNBBNKRQ RBBNKRNQ NRBKNBQR RKRBBNNQ NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 1637ms
memory: 3804kb
input:
GAME 1 2 1 1 1 2 8 GAME 2 2 0 2 3 1 8 GAME 3 1 3 8 GAME 4 2 0 3 2 2 8 GAME 5 2 0 3 3 3 8 GAME 6 1 2 5 1 2 8 GAME 7 4 4 1 8 GAME 8 3 2 1 4 8 GAME 9 2 2 3 6 8 GAME 10 2 1 2 3 1 8 GAME 11 1 3 5 1 8 GAME 12 1 3 5 3 8 GAME 13 4 3 2 2 8 GAME 14 3 1 2 3 8 GAME 15 2 1 0 2 3 8 GAME 16 2 0 4 2 1 8 GAME 17 1 2...
output:
RQKBBNRN NRKBBQNR NRBKQNRB RKQRNNBB RKRBBNNQ RBBQKRNN RQKBBNRN NRKBBQNR RKNNRBBQ BBNRKQRN RKRBBNNQ RBBNKRQN RQKBBNRN RNBBNKRQ RBBNKRNQ RQKBBNRN NRKBBQNR RKNNRBBQ RKNRNBBQ RKRBNNBQ RBQNKRBN RQKBBNRN NRKBBQNR RKNNRBBQ RKNRNBBQ RKRBQNBN RBNQKRBN RQKBBNRN RNBBNKRQ RKNNQRBB RKRQBNNB RKRBBNNQ RBNNKRBQ RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 1661ms
memory: 3920kb
input:
GAME 1 2 3 3 2 2 8 GAME 2 2 4 2 3 8 GAME 3 1 1 0 1 2 8 GAME 4 0 2 4 1 8 GAME 5 0 4 5 8 GAME 6 0 3 2 4 8 GAME 7 1 0 4 2 2 8 GAME 8 1 0 5 1 1 8 GAME 9 0 1 1 2 3 8 GAME 10 3 1 3 3 8 GAME 11 2 1 0 0 4 8 GAME 12 1 3 4 1 4 8 GAME 13 1 0 4 3 1 8 GAME 14 0 2 0 2 8 GAME 15 0 2 1 1 1 8 GAME 16 1 0 6 2 8 GAME ...
output:
RQKBBNRN NRKBBQNR RBNKBNQR RKRBNQBN RKRBBNNQ QRNBKNBR RQKBBNRN NRKBBQNR RKBBRNNQ RKRBNNBQ NRQBKNBR RQKBBNRN RNBBNKRQ BBRKRNQN RKQNNRBB RKRBBQNN NRNBKQBR RQKBBNRN NRQKNRBB RBNNQKBR RKRBNQBN QRNNKBBR RQKBBNRN NRQKNRBB RKQNNBBR NRQNKBBR RQKBBNRN NRQKNRBB RNQNKRBB BRKQNBNR NRNQKBBR RQKBBNRN RNBBNKRQ NBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 1652ms
memory: 4004kb
input:
GAME 1 1 1 2 2 2 8 GAME 2 0 1 4 4 8 GAME 3 1 1 3 4 2 8 GAME 4 1 0 3 2 2 8 GAME 5 1 0 4 0 1 8 GAME 6 0 2 4 2 8 GAME 7 0 0 0 2 8 GAME 8 1 1 0 0 0 8 GAME 9 0 1 4 6 8 GAME 10 0 1 2 2 8 GAME 11 1 0 3 4 0 8 GAME 12 0 3 4 0 8 GAME 13 3 1 1 2 2 8 GAME 14 3 1 1 2 1 8 GAME 15 2 0 3 3 1 8 GAME 16 4 3 4 1 8 GAM...
output:
RQKBBNRN RNBBNKRQ BBRKRNQN QRKNBRNB RKRBBNNQ QBBRKNNR RQKBBNRN NRQKNRBB NRBKQBNR NNBRKRQB NBBRKQNR RQKBBNRN RNBBNKRQ BBRKRNQN RBKNBNQR RKRBBNQN NBBRKNQR RQKBBNRN RNBBNKRQ NBRNKRBQ RQKNNBBR RKRBQNBN QBNRKNBR RQKBBNRN RNBBNKRQ NBRNKRBQ RKRNBBNQ RKNRBBQN NBQRKNBR RQKBBNRN NRQKNRBB RBNNQKBR RKRBNQBN NBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 1663ms
memory: 4064kb
input:
GAME 1 0 1 2 3 2 8 GAME 2 0 0 2 1 8 GAME 3 0 1 1 3 8 GAME 4 2 3 1 1 3 8 GAME 5 1 3 1 1 3 8 GAME 6 1 4 1 4 8 GAME 7 1 1 2 4 3 8 GAME 8 1 1 2 2 3 8 GAME 9 1 1 3 5 8 GAME 10 0 2 5 3 8 GAME 11 0 3 1 1 8 GAME 12 0 2 6 1 8 GAME 13 2 4 2 2 8 GAME 14 3 5 5 8 GAME 15 2 4 1 2 8 GAME 16 1 4 1 3 8 GAME 17 2 3 1...
output:
RQKBBNRN NRQKNRBB NRBKQBNR RKRQNBBN RKRBBNNQ BBRQNKNR RQKBBNRN NRQKNRBB RBKNRQBN RKNRBQNB BBRNQKNR RQKBBNRN NRQKNRBB NRBKQBNR RKRNBBQN BBRNNKQR RQKBBNRN NRKBBQNR RBNKBNQR RBKRNNBQ RKRBBNNQ BQRBNKNR RQKBBNRN RNBBNKRQ RBBNKRNQ NRBKNBQR RKRBBNNQ BNRBQKNR RQKBBNRN RNBBNKRQ NRQNBKRB BNRBKNRQ BNRBNKQR RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 1641ms
memory: 3784kb
input:
GAME 1 5 4 3 8 GAME 2 4 2 2 1 8 GAME 3 3 4 4 3 8 GAME 4 3 3 1 4 8 GAME 5 2 2 6 3 8 GAME 6 2 2 5 2 8 GAME 7 2 3 2 3 1 8 GAME 8 2 3 3 1 1 8 GAME 9 1 2 1 1 8 GAME 10 0 3 2 5 8 GAME 11 0 2 2 1 1 8 GAME 12 0 1 4 0 8 GAME 13 2 3 2 3 2 8 GAME 14 2 4 3 3 8 GAME 15 1 3 1 5 1 8 GAME 16 0 2 2 1 2 8 GAME 17 0 3...
output:
RQKBBNRN RKNRBNQB RKNBRQBN RQNBBNKR RQKBBNRN RQKNBRNB NRQKBBRN RKBRNBNQ RNQBBNKR RQKBBNRN NRNBBKQR RKNRBQNB RKRBBNNQ RNNBBQKR RQKBBNRN NRNBBKQR QRKBNNBR RKNNBRQB RQNNBBKR RQKBBNRN NRKBBQNR RNQKBBNR RKRNBQNB RNQNBBKR RQKBBNRN NRKBBQNR RNQKBBNR RKRBBNQN RNNQBBKR RQKBBNRN NRKBBQNR RBNKBNQR RQNBNKBR RKB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed