QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165493 | #7179. Fischer's Chess Guessing Game | ucup-team1600# | AC ✓ | 50ms | 4644kb | C++23 | 5.4kb | 2023-09-05 18:49:33 | 2023-09-05 18:49:35 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
inline bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL
const int max_n = -1, inf = 1000111222;
mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
return uniform_real_distribution<ld>(l, r)(rng);
}
int MX = 0;
map <set <string>, string> to_ask;
inline int rec (vector <string> have, int d = 1, bool gg = true) {
if (have.empty()) {
return d - 1;
}
// LOG(d);
umax(MX, d);
int mx = inf;
vector <int> can;
// shuffle(all(have), rng);
int y = 0;
for (int i = 0; i < len(have); i++) {
int cnt[9] = {};
for (auto &j : have) {
int cur = 0;
for (int k = 0; k < 8; k++) {
if (have[i][k] == j[k]) {
++cur;
}
}
++cnt[cur];
}
int val = 0;
for (int j = 0; j < 8; j++) {
umax(val, cnt[j]);
}
if (umin(mx, val)) {
y = 0;
can.clear();
}
if (mx == val) {
++y;
can.pb(i);
}
}
int res = inf;
LOG(len(can));
int best = -1;
for (int pos : can) {
vector<string> nice[9];
for (auto &j: have) {
int cur = 0;
for (int k = 0; k < 8; k++) {
if (have[pos][k] == j[k]) {
++cur;
}
}
nice[cur].pb(j);
}
int cur = 0;
for (int j = 0; j < 8; j++) {
umax(cur, rec(nice[j], d + 1, false));
}
if (umin(res, cur)) {
best = pos;
}
}
if (gg) {
int pos = best;
vector<string> nice[9];
for (auto &j: have) {
int cur = 0;
for (int k = 0; k < 8; k++) {
if (have[pos][k] == j[k]) {
++cur;
}
}
nice[cur].pb(j);
}
for (int j = 0; j < 8; j++) {
rec(nice[j], d + 1, true);
}
set <string> s(all(have));
assert(!to_ask.count(s));
to_ask[s] = have[pos];
}
return res;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s = "RQKBBNRN";
sort(all(s));
vector <string> can;
do {
bool ok = true;
map <char, vector <int> > have;
for (int i = 0; i < 8; i++) {
have[s[i]].pb(i);
}
if ((have['B'][0] ^ have['B'][1]) % 2 == 0) {
ok = false;
}
if (have['K'][0] < have['R'][0] || have['K'][0] > have['R'][1]) {
ok = false;
}
if (ok) {
can.pb(s);
}
} while (next_permutation(all(s)));
// LOG(len(can));
// LOG(rec(can));
// LOG(MX);
rec(can);
string game;
int num;
while (cin >> game) {
if (game == "END") {
break;
}
cin >> num;
set<string> cur(all(can));
while (true) {
string A = to_ask[cur];
cout << A << endl;
int res;
cin >> res;
if (res == 8) {
break;
}
set <string> new_cur;
for (auto &j : cur) {
int cc = 0;
for (int k = 0; k < 8; k++) {
if (A[k] == j[k]) {
++cc;
}
}
if (cc == res) {
new_cur.insert(j);
}
}
cur.swap(new_cur);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 35ms
memory: 4308kb
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: 46ms
memory: 4376kb
input:
GAME 1 1 2 2 1 2 8 GAME 2 2 1 0 1 2 8 GAME 3 1 2 2 0 3 8 GAME 4 1 2 1 1 3 8 GAME 5 2 2 0 3 0 8 GAME 6 2 1 2 1 3 8 GAME 7 0 2 3 4 3 8 GAME 8 1 2 1 0 3 8 GAME 9 0 3 2 4 8 GAME 10 0 3 1 6 8 GAME 11 0 5 3 2 8 GAME 12 1 1 2 2 3 8 GAME 13 1 2 2 3 4 8 GAME 14 0 4 3 4 8 GAME 15 1 2 1 0 1 8 GAME 16 1 1 5 8 G...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN QNRNBKRB RKRBBQNN NRBBNKQR RBBNKQNR QRKNNRBB NBNRBKRQ BQNBRNKR RKRBBNQN NRBBNKQR BNRKQBNR RNBQKRNB BRNQKBRN RBKNBQNR RKRBBNNQ NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR QBRKNRBN RKRBQNBN NRBBNKQR RBBNKQNR NBNQBRKR BRKBRQNN QRBKRNNB RKRBNQBN NRBBNKQR RBBNKQNR QRKNNRBB NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 47ms
memory: 4348kb
input:
GAME 1 2 3 2 2 3 8 GAME 2 2 4 2 8 GAME 3 3 0 5 2 8 GAME 4 3 0 2 2 8 GAME 5 2 2 2 1 2 8 GAME 6 3 0 3 2 4 8 GAME 7 1 3 0 2 4 8 GAME 8 1 3 0 3 8 GAME 9 2 3 4 1 8 GAME 10 2 3 5 4 8 GAME 11 2 2 3 2 4 8 GAME 12 1 3 0 4 8 GAME 13 0 2 3 8 GAME 14 1 0 1 4 8 GAME 15 0 1 2 4 1 8 GAME 16 0 2 2 2 2 8 GAME 17 1 0...
output:
NRBBNKQR RBBNKQNR RKBNNBRQ BRKNQBNR RBKQNNBR RKQBBNNR NRBBNKQR RBBNKQNR BBRNNQKR RKNBBQNR NRBBNKQR NRBQKBRN RBNNBKQR RBQNNKBR RKNBBNQR NRBBNKQR NRBQKBRN RBNNBKQR BNRBQKNR RKQBNNBR NRBBNKQR RBBNKQNR NBNQBRKR BRNNKRQB NNQRKBBR RKNBQNBR NRBBNKQR NRBQKBRN RBNNBKQR BBQRNKNR QNNBRKBR RKNBNQBR NRBBNKQR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 45ms
memory: 4408kb
input:
GAME 1 1 2 1 0 8 GAME 2 3 4 3 5 8 GAME 3 2 1 2 8 GAME 4 1 1 2 4 8 GAME 5 2 2 2 2 0 8 GAME 6 3 2 3 1 2 8 GAME 7 2 0 5 5 8 GAME 8 2 0 6 5 8 GAME 9 3 3 0 2 8 GAME 10 2 0 3 3 8 GAME 11 2 0 4 1 5 8 GAME 12 3 2 3 2 8 GAME 13 2 2 0 8 GAME 14 3 2 5 8 GAME 15 2 1 2 4 8 GAME 16 1 3 1 1 8 GAME 17 2 1 3 4 8 GAM...
output:
NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR QRKRBBNN NRBBNKQR NRBQKBRN NBBRQKRN NRKBBQRN NRKRBBQN NRBBNKQR RBBNKQNR QRKNNRBB NRKRBBNQ NRBBNKQR BNRKQBNR RNKQNRBB QNBRKNRB QRKRBNNB NRBBNKQR RBBNKQNR NBNQBRKR BRNNKRQB BQRNNBKR NRKRBQNB NRBBNKQR NRBQKBRN BRKBNNRQ BRNBKQNR NNRBBKRQ NRKRBNQB NRBBNKQR RBBNKQNR NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 50ms
memory: 4400kb
input:
GAME 1 0 4 3 3 8 GAME 2 0 3 3 8 GAME 3 0 4 4 3 8 GAME 4 0 5 5 3 8 GAME 5 0 4 4 4 8 GAME 6 0 6 4 6 8 GAME 7 1 3 1 3 8 GAME 8 3 2 1 2 2 8 GAME 9 2 4 2 2 8 GAME 10 0 1 0 6 8 GAME 11 1 1 2 0 4 8 GAME 12 0 2 3 4 8 GAME 13 1 1 4 1 6 8 GAME 14 0 3 6 8 GAME 15 1 1 4 1 8 GAME 16 2 3 3 1 1 8 GAME 17 1 4 2 1 8...
output:
NRBBNKQR RKNNRQBB RBKNRNBQ RKNNBBRQ RQNKRBBN NRBBNKQR RKNNRQBB RBKNQRBN RNQKRBBN NRBBNKQR RKNNRQBB RBKNRNBQ RNKNQRBB RNNKRBBQ NRBBNKQR RKNNRQBB RKNRQNBB RKNRBQNB RQNKRNBB NRBBNKQR RKNNRQBB RBKNRNBQ RNKNQRBB RNQKRNBB NRBBNKQR RKNNRQBB RKNNRBBQ RNKNRQBB RNNKRQBB NRBBNKQR BNRKQBNR BQRKNNRB BBNNQRKR RBB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 39ms
memory: 4612kb
input:
GAME 1 3 5 2 8 GAME 2 3 6 8 GAME 3 4 4 2 3 8 GAME 4 3 3 2 3 4 8 GAME 5 3 4 4 4 8 GAME 6 4 3 2 0 8 GAME 7 1 2 0 3 8 GAME 8 2 0 4 4 8 GAME 9 2 0 3 2 8 GAME 10 1 1 1 4 3 8 GAME 11 2 0 2 3 1 8 GAME 12 2 1 2 3 8 GAME 13 3 2 3 4 8 GAME 14 2 2 2 3 8 GAME 15 4 5 8 GAME 16 4 5 5 8 GAME 17 4 4 3 4 8 GAME 18 6...
output:
NRBBNKQR NRBQKBRN NRBQKRNB QRBKNBRN NRBBNKQR NRBQKBRN NRBKQBRN NRBBNKQR RNBKNBQR RKBBNQNR BRKNNBQR NRBKNBRQ NRBBNKQR NRBQKBRN RNBBQKRN NRQNBKRB NRBKQRNB QRBKNNRB NRBBNKQR NRBQKBRN NBBRQKRN NNBQRKRB NRBKQNRB NRBBNKQR RNBKNBQR NBBRKNQR BNNBRKQR NRBKNQRB NRBBNKQR BNRKQBNR RNBQKRNB NBRKBNRQ QRNKBBRN NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 45ms
memory: 4568kb
input:
GAME 1 1 1 3 8 GAME 2 2 5 3 8 GAME 3 1 1 2 2 4 8 GAME 4 0 3 6 5 8 GAME 5 0 3 5 3 8 GAME 6 0 4 5 8 GAME 7 2 4 0 6 8 GAME 8 3 3 5 3 8 GAME 9 2 4 0 8 GAME 10 1 1 3 5 2 8 GAME 11 1 2 8 GAME 12 2 4 1 3 4 8 GAME 13 1 0 4 4 2 8 GAME 14 1 1 4 2 6 8 GAME 15 1 1 4 2 8 GAME 16 0 5 4 5 8 GAME 17 0 4 3 2 8 GAME ...
output:
NRBBNKQR BNRKQBNR RNKQNRBB RBBQKRNN NRBBNKQR RBBNKQNR RBBKQNNR RBBNKRQN NRBBNKQR BNRKQBNR RNKQNRBB QNBRKNRB RBQNKNBR RBBNKRNQ NRBBNKQR RKNNRQBB RBKNQRBN RBNKQRBN RBQNKRBN NRBBNKQR RKNNRQBB RBKNQRBN RBKNBQRN RBNQKRBN NRBBNKQR RKNNRQBB RBKNRNBQ RBNNKRBQ NRBBNKQR RBBNKQNR BBRNNQKR RNBBKRNQ RQBBKRNN NRB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 49ms
memory: 4644kb
input:
GAME 1 3 2 3 5 8 GAME 2 4 1 3 6 8 GAME 3 4 1 4 8 GAME 4 2 3 2 4 4 8 GAME 5 3 4 1 4 8 GAME 6 3 5 4 8 GAME 7 0 0 6 4 8 GAME 8 1 2 2 3 2 8 GAME 9 0 1 3 5 8 GAME 10 1 3 3 3 4 8 GAME 11 2 1 1 2 8 GAME 12 1 4 3 8 GAME 13 0 2 1 2 8 GAME 14 0 1 3 8 GAME 15 1 3 3 3 8 GAME 16 0 2 1 3 8 GAME 17 1 1 3 5 8 GAME ...
output:
NRBBNKQR NRBQKBRN BRKBNNRQ BRNBKQNR QRNBKNBR NRBBNKQR RNBKNBQR QRNBBKNR NRKBQNBR NRQBKNBR NRBBNKQR RNBKNBQR QRNBBKNR NRNBKQBR NRBBNKQR RBBNKQNR RKBNNBRQ BRKNQBNR BNRNKBQR QRNNKBBR NRBBNKQR NRBQKBRN NBBRQKRN NRNQBBKR NRQNKBBR NRBBNKQR NRBQKBRN NRBQKRNB NRNQKBBR NRBBNKQR RKNNRQBB BBQRKRNN BBQRKNRN BBR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 43ms
memory: 4308kb
input:
GAME 1 2 5 5 8 GAME 2 3 3 1 4 8 GAME 3 4 3 8 GAME 4 1 1 1 2 2 8 GAME 5 2 3 0 3 3 8 GAME 6 2 4 3 1 2 8 GAME 7 2 4 1 8 GAME 8 3 4 3 1 8 GAME 9 4 5 3 8 GAME 10 1 3 0 8 GAME 11 2 2 3 2 5 8 GAME 12 2 2 2 1 8 GAME 13 3 4 5 3 8 GAME 14 2 4 2 1 4 8 GAME 15 3 2 3 0 8 GAME 16 1 0 1 5 8 GAME 17 1 0 3 2 8 GAME ...
output:
NRBBNKQR RBBNKQNR RBBKQNNR QBBRKNNR NRBBNKQR NRBQKBRN RNBBQKRN NBBQRNKR NBBRKQNR NRBBNKQR RNBKNBQR NBBRKNQR NRBBNKQR BNRKQBNR RNKQNRBB BRQNKNRB BBNQRKRN QBNRKNBR NRBBNKQR RBBNKQNR RKBNNBRQ BBNRQKNR BQRBKNNR NBQRKNBR NRBBNKQR RBBNKQNR BBRNNQKR RKBNNQRB BRQNKBNR NBNRKQBR NRBBNKQR RBBNKQNR BBRNNQKR QNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 48ms
memory: 4352kb
input:
GAME 1 3 1 2 3 8 GAME 2 2 4 5 5 8 GAME 3 4 3 3 1 8 GAME 4 4 2 3 3 8 GAME 5 3 0 2 8 GAME 6 5 8 GAME 7 2 4 4 5 8 GAME 8 3 2 0 3 8 GAME 9 4 2 4 8 GAME 10 3 0 4 6 8 GAME 11 4 2 4 5 8 GAME 12 3 1 3 2 2 8 GAME 13 3 0 3 3 8 GAME 14 4 1 5 8 GAME 15 5 6 8 GAME 16 4 3 1 8 GAME 17 5 5 3 8 GAME 18 4 2 4 4 8 GAM...
output:
NRBBNKQR NRBQKBRN NNRBBQKR NBQNRKBR BBRQNKNR NRBBNKQR RBBNKQNR BBRNNQKR BBRNKNQR BBRNQKNR NRBBNKQR RNBKNBQR NBBRKNQR NNBBQRKR BBRNNKQR NRBBNKQR RNBKNBQR NBBRQKNR NNQBRKBR BQRBNKNR NRBBNKQR NRBQKBRN RBNNBKQR BNRBQKNR NRBBNKQR BNRBNKQR NRBBNKQR RBBNKQNR BBRNNQKR BBQNRKNR QBRNBKNR NRBBNKQR NRBQKBRN BRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 41ms
memory: 4336kb
input:
GAME 1 2 2 4 4 8 GAME 2 2 2 3 4 2 8 GAME 3 2 3 1 4 4 8 GAME 4 1 2 1 3 2 8 GAME 5 1 3 0 3 4 8 GAME 6 1 3 0 4 4 8 GAME 7 4 2 1 6 8 GAME 8 3 1 3 2 8 GAME 9 4 2 1 8 GAME 10 3 2 3 3 8 GAME 11 3 3 0 5 8 GAME 12 2 2 3 4 8 GAME 13 5 3 4 3 8 GAME 14 5 2 5 4 8 GAME 15 6 5 4 5 8 GAME 16 4 4 3 5 8 GAME 17 5 2 4...
output:
NRBBNKQR RBBNKQNR NBNQBRKR NQRNBBKR RQNBBNKR NRBBNKQR RBBNKQNR NBNQBRKR BNNBRQKR BRNNQBKR RNQBBNKR NRBBNKQR RBBNKQNR RKBNNBRQ RQNBKNBR RBNKBNQR RNNBBQKR NRBBNKQR BNRKQBNR RNBQKRNB BBNQRNKR QBRNKNBR RQNNBBKR NRBBNKQR BNRKQBNR BQRKNNRB QNNRKBBR RKNQBBNR RNQNBBKR NRBBNKQR BNRKQBNR BQRKNNRB QNNRKBBR RKN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed