QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283801 | #7179. Fischer's Chess Guessing Game | Misuki | AC ✓ | 1297ms | 3824kb | C++20 | 3.5kb | 2023-12-15 15:03:30 | 2023-12-15 15:03:31 |
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];
}
int match(string s, string t) {
int res = 0;
for(int i = 0; i < 8; i++)
res += s[i] == t[i];
return res;
}
array<string, 960> state;
array<bool, 960> cand;
int mxGroupSize(string qs) {
array<int, 9> cnt = {};
for(int i = 0; string &s : state)
if (cand[i++])
cnt[match(qs, s)]++;
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()));
}
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++;
string qs;
int mn = INT_MAX;
for(int i = 0; string &s : state)
if (int tmp = mxGroupSize(s); tmp - cand[i++] < mn)
mn = tmp, qs = s;
cout << qs << endl;
int res; cin >> res;
//int res = match(qs, sol);
for(int i = 0; string &s : state) {
if (cand[i])
cand[i] = match(qs, s) == res;
i++;
}
if (res == 8)
done = true;
}
if (!done and guess == 6)
return 0;
cin >> s;
}
//cout << "correct!\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 3824kb
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: 1265ms
memory: 3612kb
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: 1171ms
memory: 3556kb
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: 1261ms
memory: 3612kb
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: 1271ms
memory: 3584kb
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: 1286ms
memory: 3600kb
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: 1267ms
memory: 3540kb
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: 1297ms
memory: 3788kb
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: 1258ms
memory: 3604kb
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: 1291ms
memory: 3680kb
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: 1252ms
memory: 3588kb
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