QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283801#7179. Fischer's Chess Guessing GameMisukiAC ✓1297ms3824kbC++203.5kb2023-12-15 15:03:302023-12-15 15:03:31

Judging History

你现在查看的是最新测评结果

  • [2023-12-15 15:03:31]
  • 评测
  • 测评结果:AC
  • 用时:1297ms
  • 内存:3824kb
  • [2023-12-15 15:03:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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