QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283808 | #7179. Fischer's Chess Guessing Game | Misuki | AC ✓ | 272ms | 7384kb | C++20 | 3.5kb | 2023-12-15 15:28:15 | 2023-12-15 15:28:15 |
Judging History
answer
#pragma GCC optimize("O2")
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <compare>
#include <complex>
#include <concepts>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numbers>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <span>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
//#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)
namespace R = std::ranges;
namespace V = std::views;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = tuple<int, int, int>;
using ldb = long double;
//#define double ldb
template<class T>
ostream& operator<<(ostream& os, const pair<T, T> pr) {
return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
for(const T &X : arr)
os << X << ' ';
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
for(const T &X : vec)
os << X << ' ';
return os;
}
bool valid(string s) {
array<int, 2> posR = {-1, -1}, posB = {-1, -1};
int posK = -1;
for(int i = 0; i < ssize(s); i++) {
if (s[i] == 'K')
posK = i;
if (s[i] == 'R')
posR[posR[0] != -1] = i;
if (s[i] == 'B')
posB[posB[0] != -1] = i;
}
return posB[0] % 2 != posB[1] % 2 and posR[0] < posK and posK < posR[1];
}
array<string, 960> state;
array<bool, 960> cand;
int match[960][960];
int mxGroupSize(int j) {
array<int, 9> cnt = {};
for(int i = 0; i < 960; i++)
if (cand[i])
cnt[match[i][j]]++;
return R::max(cnt);
}
signed main() {
//ios::sync_with_stdio(false), cin.tie(NULL);
{
string s = "BBKNNQRR";
int ptr = 0;
do {
if (valid(s))
state[ptr++] = s;
} while(next_permutation(s.begin(), s.end()));
}
for(int i = 0; i < 960; i++)
for(int j = 0; j < 960; j++)
for(int k = 0; k < 8; k++)
match[i][j] += state[i][k] == state[j][k];
string s; cin >> s;
while(s != "END") {
int t; cin >> t;
fill(cand.begin(), cand.end(), true);
bool done = false;
int guess = 0;
while(guess < 6 and !done) {
guess++;
int qs;
int mn = INT_MAX;
for(int i = 0; i < 960; i++)
if (int tmp = mxGroupSize(i); tmp - cand[i] < mn)
mn = tmp, qs = i;
cout << state[qs] << endl;
int res; cin >> res;
//int res = match(qs, sol);
for(int i = 0; i < 960; i++)
if (cand[i])
cand[i] = match[qs][i] == res;
if (res == 8)
done = true;
}
if (!done and guess == 6)
return 0;
cin >> s;
}
//cout << "correct!\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7204kb
input:
GAME 1 3 0 3 8 END
output:
RQKNBBRN NRKQNBBR BNRBQKRN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 4 (1 test case)
Test #2:
score: 0
Accepted
time: 251ms
memory: 7252kb
input:
GAME 1 3 0 3 8 GAME 2 3 0 3 6 8 GAME 3 2 2 4 3 8 GAME 4 2 0 2 3 8 GAME 5 2 0 1 4 8 GAME 6 1 0 3 1 8 GAME 7 4 3 2 5 8 GAME 8 5 4 0 8 GAME 9 4 4 4 4 8 GAME 10 2 3 2 0 8 GAME 11 3 0 1 3 8 GAME 12 3 0 1 2 8 GAME 13 3 4 3 8 GAME 14 4 3 2 8 GAME 15 3 3 2 3 8 GAME 16 1 0 5 3 8 GAME 17 2 0 4 1 4 8 GAME 18 2...
output:
RQKNBBRN NRKQNBBR BNRBQKRN RKRBBQNN RQKNBBRN NRKQNBBR BNRBQKRN RKRBBQNN RKRBBNQN RQKNBBRN NRKQBBNR RBNKBRNQ RNBKRBNQ RKRBBNNQ RQKNBBRN NRKQBBNR BNRNQKRB RKNNRQBB RKRBQNBN RQKNBBRN NRKQBBNR BNRNQKRB RNKBQRBN RKRBNQBN RQKNBBRN NRQNBBKR RKBQRNNB BNRQKRNB RKRBNNBQ RQKNBBRN RQBNKBNR BRQKNBRN RKRNQBBN RKR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #3:
score: 0
Accepted
time: 238ms
memory: 7220kb
input:
GAME 1 2 3 3 2 8 GAME 2 2 3 4 4 8 GAME 3 2 2 3 3 8 GAME 4 1 2 3 4 8 GAME 5 1 1 3 2 8 GAME 6 1 1 4 6 8 GAME 7 4 5 2 8 GAME 8 3 3 3 1 8 GAME 9 4 4 5 4 8 GAME 10 3 4 4 8 GAME 11 2 3 3 6 8 GAME 12 3 3 2 3 5 8 GAME 13 4 2 3 8 GAME 14 4 1 4 3 8 GAME 15 3 1 2 4 8 GAME 16 3 2 1 1 8 GAME 17 3 3 0 1 8 GAME 18...
output:
RQKNBBRN NRKQBBNR RBNNBKQR RNNQKBBR RKQBBNNR RQKNBBRN NRKQBBNR RBNNBKQR RNKBBRNQ RKNBBQNR RQKNBBRN NRKQBBNR RBNKBRNQ BNNBQRKR RKNBBNQR RQKNBBRN NRQNBBKR BQRBNKNR QBRKNNBR RKQBNNBR RQKNBBRN NRQNBBKR RNBBNKQR BNNBRKRQ RKNBQNBR RQKNBBRN NRQNBBKR RNBBNKQR RNNBKQBR RKNBNQBR RQKNBBRN RQBNKBNR BQNBRKNR RKQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #4:
score: 0
Accepted
time: 252ms
memory: 7220kb
input:
GAME 1 4 2 3 5 8 GAME 2 4 1 2 5 8 GAME 3 3 4 1 4 8 GAME 4 2 4 1 8 GAME 5 2 5 4 8 GAME 6 2 4 0 4 8 GAME 7 3 5 6 8 GAME 8 3 5 8 GAME 9 2 4 1 3 8 GAME 10 1 1 1 3 8 GAME 11 1 2 0 6 8 GAME 12 1 2 1 1 8 GAME 13 2 3 0 4 1 8 GAME 14 2 2 0 6 8 GAME 15 1 1 1 0 5 8 GAME 16 3 4 1 2 8 GAME 17 4 2 4 2 8 GAME 18 3...
output:
RQKNBBRN RQBNKBNR RNKQRBBN RBKRBQNN QRKRBBNN RQKNBBRN RQBNKBNR RNKBBNRQ NRQKBBRN NRKRBBQN RQKNBBRN NRKQNBBR RQKBNNBR NRQNBBKR NRKRBBNQ RQKNBBRN NRKQBBNR RQBNKBNR QRKRBNNB RQKNBBRN NRKQBBNR QRKBBNNR NRKRBQNB RQKNBBRN NRKQBBNR RQBNKBNR NRNQBKRB NRKRBNQB RQKNBBRN NRKQNBBR NRKRQBBN QRKRNBBN RQKNBBRN NRK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #5:
score: 0
Accepted
time: 257ms
memory: 7184kb
input:
GAME 1 4 3 3 3 8 GAME 2 3 2 4 5 8 GAME 3 2 1 0 1 8 GAME 4 2 0 1 2 8 GAME 5 1 1 2 0 8 GAME 6 1 0 3 2 8 GAME 7 2 1 1 2 5 8 GAME 8 2 0 0 2 8 GAME 9 1 0 3 2 2 8 GAME 10 3 0 1 8 GAME 11 3 0 1 6 8 GAME 12 2 2 8 GAME 13 2 0 0 3 8 GAME 14 2 0 1 5 3 8 GAME 15 1 0 1 2 8 GAME 16 2 1 1 2 8 GAME 17 1 0 4 3 8 GAM...
output:
RQKNBBRN RQBNKBNR BRQKNBRN RKQRBBNN RQNKRBBN RQKNBBRN NRKQNBBR RNNKBBQR NNRKRBBQ RNQKRBBN RQKNBBRN NRKQBBNR BQRBKNRN RBBNNQKR RNNKRBBQ RQKNBBRN NRKQBBNR BNRNQKRB RNKBQRBN RQNKRNBB RQKNBBRN NRQNBBKR RNBBNKQR QRBBKRNN RNQKRNBB RQKNBBRN NRQNBBKR RKBQRNNB BNRQKRNB RNNKRQBB RQKNBBRN NRKQBBNR BQRBKNRN RNK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #6:
score: 0
Accepted
time: 264ms
memory: 7196kb
input:
GAME 1 3 3 4 8 GAME 2 3 3 5 3 8 GAME 3 2 3 0 4 8 GAME 4 1 1 2 3 8 GAME 5 1 2 0 4 8 GAME 6 1 2 1 0 2 8 GAME 7 4 1 2 6 8 GAME 8 4 1 2 8 GAME 9 3 3 8 GAME 10 2 2 3 1 0 8 GAME 11 2 3 1 3 8 GAME 12 2 3 2 0 2 8 GAME 13 1 4 3 1 8 GAME 14 1 3 1 5 4 8 GAME 15 1 3 1 6 5 8 GAME 16 1 3 1 6 8 GAME 17 1 4 4 5 8 G...
output:
RQKNBBRN NRKQNBBR NRNKBBRQ QRBKNBRN RQKNBBRN NRKQNBBR NRNKBBRQ NRKBBNRQ NRBKQBRN RQKNBBRN NRKQBBNR RBNNBKQR QRBKRBNN NRBKNBRQ RQKNBBRN NRQNBBKR RNBBNKQR QRBBKRNN QRBKNNRB RQKNBBRN NRQNBBKR BQRBNKNR NRKQRNBB NRBKQNRB RQKNBBRN NRQNBBKR BQRBNKNR BBNRKRQN NRKBRNBQ NRBKNQRB RQKNBBRN RQBNKBNR RNKBBNRQ NRQ...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #7:
score: 0
Accepted
time: 243ms
memory: 7136kb
input:
GAME 1 2 2 4 3 2 8 GAME 2 3 0 1 4 2 8 GAME 3 2 1 1 1 8 GAME 4 3 1 0 2 8 GAME 5 2 1 2 2 2 8 GAME 6 2 0 1 3 4 8 GAME 7 3 0 2 8 GAME 8 2 0 1 5 8 GAME 9 1 0 3 4 8 GAME 10 3 0 0 4 8 GAME 11 1 0 5 4 8 GAME 12 2 0 3 6 8 GAME 13 3 1 2 1 8 GAME 14 2 0 1 6 8 GAME 15 1 0 1 1 8 GAME 16 3 1 3 2 8 GAME 17 2 0 3 8...
output:
RQKNBBRN NRKQBBNR RBNKBRNQ RNBKRBNQ RKRBBNNQ RBBQKRNN RQKNBBRN NRKQNBBR BNRBQKRN RBQKBRNN RBNKBNRQ RBBNKRQN RQKNBBRN NRKQBBNR BQRBKNRN RNKRQNBB RBBNKRNQ RQKNBBRN NRKQNBBR NQNRBKRB RNBKRBQN RBQNKRBN RQKNBBRN NRKQBBNR BQRBKNRN BRNBQKRN RKBBRQNN RBNQKRBN RQKNBBRN NRKQBBNR BNRNQKRB RNKBQRBN RQNKNRBB RBN...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #8:
score: 0
Accepted
time: 272ms
memory: 7384kb
input:
GAME 1 0 2 4 5 8 GAME 2 0 3 5 3 8 GAME 3 0 1 0 6 8 GAME 4 2 3 3 5 8 GAME 5 2 4 4 8 GAME 6 1 4 8 GAME 7 1 0 2 5 3 8 GAME 8 2 0 3 3 0 8 GAME 9 1 1 0 5 8 GAME 10 2 1 6 4 8 GAME 11 1 0 0 3 8 GAME 12 0 1 4 2 8 GAME 13 2 1 4 1 3 8 GAME 14 0 1 5 4 8 GAME 15 1 1 2 2 3 8 GAME 16 2 0 2 2 8 GAME 17 1 1 0 4 8 G...
output:
RQKNBBRN BBQRNNKR QRBBNKNR NRBBKNQR QRNBKNBR RQKNBBRN BBQRNNKR NRBBQNKR QNBBRNKR NRQBKNBR RQKNBBRN BBQRNNKR BQRKNRNB NRNBQKBR NRNBKQBR RQKNBBRN NRKQBBNR RBNNBKQR RNNQKBBR QRNNKBBR RQKNBBRN NRKQBBNR RQBNKBNR NRQNKBBR RQKNBBRN NRQNBBKR NRNQKBBR RQKNBBRN NRQNBBKR RKBQRNNB BBRKRQNN QBRKRNBN BBRQKRNN RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #9:
score: 0
Accepted
time: 250ms
memory: 7132kb
input:
GAME 1 0 4 3 8 GAME 2 0 3 3 5 8 GAME 3 0 4 2 3 8 GAME 4 0 4 2 4 8 GAME 5 0 5 3 8 GAME 6 0 3 2 2 8 GAME 7 1 2 2 3 2 8 GAME 8 2 4 6 4 8 GAME 9 1 3 2 8 GAME 10 1 2 1 3 8 GAME 11 2 3 2 1 8 GAME 12 1 4 5 8 GAME 13 3 2 1 3 8 GAME 14 4 3 2 4 8 GAME 15 3 1 2 4 3 8 GAME 16 5 5 4 8 GAME 17 4 1 3 8 GAME 18 4 2...
output:
RQKNBBRN BBQRNNKR BNRBKQNR QBBRKNNR RQKNBBRN BBQRNNKR NRBBQNKR NBRNKQBR NBBRKQNR RQKNBBRN BBQRNNKR BNRBKQNR BBNRKQRN NBBRKNQR RQKNBBRN BBQRNNKR BNRBKQNR BBNRKQRN QBNRKNBR RQKNBBRN BBQRNNKR BBNRNKQR NBQRKNBR RQKNBBRN BBQRNNKR NRBBQNKR BBRNNKQR NBNRKQBR RQKNBBRN NRQNBBKR BQRBNKNR RNQBKNBR RBBQNNKR QNB...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #10:
score: 0
Accepted
time: 260ms
memory: 7204kb
input:
GAME 1 0 4 4 3 8 GAME 2 1 2 5 4 3 8 GAME 3 1 2 5 3 3 8 GAME 4 1 1 4 2 2 8 GAME 5 0 2 4 2 8 GAME 6 0 3 2 6 8 GAME 7 2 3 5 3 8 GAME 8 1 3 6 8 GAME 9 2 3 6 8 GAME 10 1 2 4 8 GAME 11 0 3 2 5 8 GAME 12 1 3 4 3 8 GAME 13 1 2 5 8 GAME 14 2 4 3 4 8 GAME 15 1 3 4 1 4 8 GAME 16 0 2 5 8 GAME 17 1 2 6 8 GAME 18...
output:
RQKNBBRN BBQRNNKR BNRBKQNR BRNBNQKR BBRQNKNR RQKNBBRN NRQNBBKR BQRBNKNR QNRBBKNR NQBBRKNR BBRNQKNR RQKNBBRN NRQNBBKR BQRBNKNR QNRBBKNR BRKBNQNR BBRNNKQR RQKNBBRN NRQNBBKR RNBBNKQR RNNBKQBR NNBBRKRQ BQRBNKNR RQKNBBRN BBQRNNKR QRBBNKNR NRBBKNQR BNRBQKNR RQKNBBRN BBQRNNKR NRBBQNKR BBRNNKQR BNRBNKQR RQK...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Test #11:
score: 0
Accepted
time: 245ms
memory: 7156kb
input:
GAME 1 3 1 3 4 8 GAME 2 2 2 2 6 8 GAME 3 2 2 3 5 8 GAME 4 5 5 1 8 GAME 5 4 4 8 GAME 6 3 3 3 2 8 GAME 7 0 6 2 8 GAME 8 0 4 3 2 8 GAME 9 0 4 4 8 GAME 10 2 3 2 5 8 GAME 11 1 4 5 2 8 GAME 12 2 3 3 3 1 8 GAME 13 0 4 2 0 8 GAME 14 0 3 8 GAME 15 0 3 6 8 GAME 16 2 3 2 3 8 GAME 17 1 5 3 8 GAME 18 2 4 4 5 8 G...
output:
RQKNBBRN NRKQNBBR NQNRBKRB BQNBRKNR RQNBBNKR RQKNBBRN NRKQBBNR RBNKBRNQ RKQBBNNR RNQBBNKR RQKNBBRN NRKQBBNR RBNKBRNQ BNNBQRKR RNNBBQKR RQKNBBRN RBNNBKQR BBNQRKRN RQNNBBKR RQKNBBRN RQBNKBNR RNQNBBKR RQKNBBRN NRKQNBBR NRNKBBRQ NNRKBRQB RNNQBBKR RQKNBBRN BBQRNNKR BBNRKQNR BRQBNNKR RQKNBBRN BBQRNNKR BNR...
result:
ok (c) correct after 96 tests, max moves 6 (96 test cases)
Extra Test:
score: 0
Extra Test Passed