QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165994#7179. Fischer's Chess Guessing Gameucup-team987#AC ✓666ms3556kbC++234.8kb2023-09-05 23:56:392023-09-05 23:56:40

Judging History

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

  • [2023-09-05 23:56:40]
  • 评测
  • 测评结果:AC
  • 用时:666ms
  • 内存:3556kb
  • [2023-09-05 23:56:39]
  • 提交

answer

#if __INCLUDE_LEVEL__ == 0

#include <bits/stdc++.h>

using namespace std;

#include __BASE_FILE__

namespace {

using S = array<char, 8>;

int get_pos(const S& s, int k) {
  for (int i : rep(8)) {
    if (s[i] == 0 && k-- == 0) {
      return i;
    }
  }
  assert(false);
}

vector<S> v;

void init() {
  for (int b0 : {0, 2, 4, 6}) {
    for (int b1 : {1, 3, 5, 7}) {
      for (int ri : rep(6)) {
        for (int ki : rep(ri)) {
          for (int li : rep(ki)) {
            for (int qi : rep(3)) {
              S s{};
              s[b0] = 'B';
              s[b1] = 'B';
              s[get_pos(s, ri)] = 'R';
              s[get_pos(s, ki)] = 'K';
              s[get_pos(s, li)] = 'R';
              s[get_pos(s, qi)] = 'Q';
              for (int i : rep(8)) {
                if (s[i] == 0) {
                  s[i] = 'N';
                }
              }
              v.push_back(s);
            }
          }
        }
      }
    }
  }
}

int get_n_correct(int i, int j) {
  int ret = 0;
  for (int k : rep(8)) {
    ret += v[i][k] == v[j][k];
  }
  return ret;
}

void solve() {
  init();
  while (true) {
    string s;
    cin >> s;
    if (s == "END") {
      break;
    }
    int game_id;
    cin >> game_id;
    bitset<960> bs;
    bs.set();
    while (true) {
      int best = -1;
      int mn = 1e9;
      for (int cand : rep(960)) {
        array<int, 9> occ{};
        for (int i : bs) {
          ++occ[get_n_correct(i, cand)];
        }
        if (chmin(mn, ranges::max(occ))) {
          best = cand;
        }
      }
      print(ALL(string, v[best]));
      int n_correct;
      cin >> n_correct;
      if (n_correct == 8) {
        break;
      }
      for (int i : bs) {
        if (get_n_correct(best, i) != n_correct) {
          bs[i] = 0;
        }
      }
      if (bs.count() == 1) {
        print(ALL(string, v[bs._Find_first()]));
        cin >> n_correct;
        assert(n_correct == 8);
        break;
      }
    }
  }
}

}  // namespace

int main() {
  ios::sync_with_stdio(false);

  solve();
}

#else  // __INCLUDE_LEVEL__

#undef assert
#define assert(expr) (expr) || (__builtin_unreachable(), 0)

#define ALL(f, r, ...) \
  [&](auto&& _) { return f(begin(_), end(_), ##__VA_ARGS__); }(r)

namespace std {

template <size_t N>
auto begin(const bitset<N>& x) {
  struct {
    const bitset<N>* p;
    size_t i;

    bool operator!=(int) const { return i < p->size(); }
    void operator++() { i = p->_Find_next(i); }
    size_t operator*() const { return i; }
  } ret{&x, x._Find_first()};
  return ret;
}

template <size_t N>
int end(const bitset<N>&) {
  return 0;
}

}  // namespace std

template <class T, class U = T>
bool chmin(T& x, U&& y) {
  return y < x && (x = forward<U>(y), true);
}

template <class T, class U = T>
bool chmax(T& x, U&& y) {
  return x < y && (x = forward<U>(y), true);
}

namespace std {

template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  return is >> p.first >> p.second;
}

template <class... Ts>
istream& operator>>(istream& is, tuple<Ts...>& t) {
  return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}

template <class... Ts>
istream& operator>>(istream& is, tuple<Ts&...>&& t) {
  return is >> t;
}

template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>
auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << ' ' << p.second;
}

template <class... Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
  auto f = [&os](const auto&... xs) -> ostream& {
    [[maybe_unused]] auto sep = "";
    ((os << exchange(sep, " ") << xs), ...);
    return os;
  };
  return apply(f, t);
}

template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>
auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << e;
  }
  return os;
}

}  // namespace std

template <class... Ts>
void print(Ts&&... xs) {
  cout << tie(xs...) << '\n';
}

inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }

#endif  // __INCLUDE_LEVEL__

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 3440kb

input:

GAME 1
1
0
3
5
8
END

output:

NRBBNKQR
BRNNKBQR
NQRKBRNB
RKBBQRNN
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 5 (1 test case)

Test #2:

score: 0
Accepted
time: 647ms
memory: 3524kb

input:

GAME 1
1
0
3
5
8
GAME 2
2
3
3
1
2
8
GAME 3
1
0
3
4
2
8
GAME 4
1
0
1
3
2
8
GAME 5
2
3
4
2
8
GAME 6
2
2
5
2
8
GAME 7
0
2
3
2
8
GAME 8
1
3
3
2
2
8
GAME 9
0
3
3
3
8
GAME 10
0
3
3
2
8
GAME 11
0
5
3
3
8
GAME 12
1
2
2
0
1
8
GAME 13
1
1
5
3
8
GAME 14
0
4
2
4
8
GAME 15
1
2
1
2
2
8
GAME 16
1
0
2
1
1
8
GAME 17...

output:

NRBBNKQR
BRNNKBQR
NQRKBRNB
RKBBQRNN
RKRBBQNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBRKRQNN
RKRBBNQN
NRBBNKQR
BRNNKBQR
NQRKBRNB
RKBBQRNN
BBRKRQNN
RKRBBNNQ
NRBBNKQR
BRNNKBQR
NQRKBRNB
QNRBBKRN
BBRKRQNN
RKRBQNBN
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RKRBNQBN
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBRKRNQN
RKRBNNBQ
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 661ms
memory: 3556kb

input:

GAME 1
2
2
5
1
8
GAME 2
2
2
4
0
2
8
GAME 3
3
1
3
1
0
8
GAME 4
3
1
2
2
1
8
GAME 5
2
3
5
0
8
GAME 6
3
1
1
3
0
8
GAME 7
1
3
5
0
8
GAME 8
1
3
3
1
1
8
GAME 9
2
1
3
2
0
8
GAME 10
2
1
0
0
1
8
GAME 11
2
1
1
3
0
8
GAME 12
1
4
3
2
8
GAME 13
0
2
4
8
GAME 14
1
1
2
3
4
8
GAME 15
0
1
0
2
8
GAME 16
0
2
2
2
8
GAME ...

output:

NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBRKRNQN
RKQBBNNR
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBRKNRQN
BBRKRQNN
RKNBBQNR
NRBBNKQR
RBBNQKRN
BRKBRNQN
BBRKNQNR
BBRKRQNN
RKNBBNQR
NRBBNKQR
RBBNQKRN
BRKBRNQN
BBRNKNQR
BBRKRNQN
RKQBNNBR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNKRNQ
RKNBQNBR
NRBBNKQR
RBBNQKRN
BRKBRNQN
BNNBRKQR
BBRKRNQN
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 666ms
memory: 3544kb

input:

GAME 1
1
2
1
3
1
8
GAME 2
3
1
4
1
8
GAME 3
2
0
3
1
1
8
GAME 4
1
1
0
2
8
GAME 5
2
0
4
0
0
8
GAME 6
3
0
1
2
2
8
GAME 7
2
1
1
0
8
GAME 8
2
2
0
0
1
8
GAME 9
3
0
0
6
8
GAME 10
2
0
4
1
0
8
GAME 11
2
1
3
1
0
8
GAME 12
3
0
0
4
8
GAME 13
2
2
3
4
5
8
GAME 14
3
1
8
GAME 15
2
1
1
3
3
8
GAME 16
1
3
0
4
8
GAME 17...

output:

NRBBNKQR
BRNNKBQR
BNRBKRQN
BRNKRBNQ
BBRKRNNQ
QRKRBBNN
NRBBNKQR
RBBNQKRN
BRKBRNQN
QNRBBNKR
NRKRBBQN
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRKNQNR
BBRKRQNN
NRKRBBNQ
NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRKRNNQ
QRKRBNNB
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBNQRNKR
BBRKRNQN
NRKRBQNB
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBNRKRQN
BBRKRNQN
NRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 661ms
memory: 3436kb

input:

GAME 1
0
4
1
1
8
GAME 2
0
3
0
3
8
GAME 3
0
4
2
3
8
GAME 4
0
5
0
2
8
GAME 5
0
4
2
2
8
GAME 6
0
6
3
8
GAME 7
1
0
3
6
4
8
GAME 8
3
4
3
3
8
GAME 9
2
2
4
4
8
GAME 10
0
1
1
4
8
GAME 11
1
2
3
2
3
8
GAME 12
0
2
5
3
8
GAME 13
1
0
2
5
3
8
GAME 14
0
3
1
1
8
GAME 15
1
1
2
1
2
8
GAME 16
2
2
3
1
2
8
GAME 17
1
0
4...

output:

NRBBNKQR
RKNNRQBB
RBKNBNRQ
BNNBQRKR
RQNKRBBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
RBKNRNBQ
RNQKRBBN
NRBBNKQR
RKNNRQBB
RBKNBNRQ
BNRKQBRN
RNNKRBBQ
NRBBNKQR
RKNNRQBB
BBRNKQRN
BBRKRQNN
RQNKRNBB
NRBBNKQR
RKNNRQBB
RBKNBNRQ
BNRKQBRN
RNQKRNBB
NRBBNKQR
RKNNRQBB
BNRKRBQN
RNNKRQBB
NRBBNKQR
BRNNKBQR
NQRKBRNB
RKBBQRNN
BBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 647ms
memory: 3492kb

input:

GAME 1
3
3
1
4
8
GAME 2
3
4
0
8
GAME 3
4
3
0
1
8
GAME 4
3
2
0
4
8
GAME 5
3
3
0
0
1
8
GAME 6
4
2
1
3
8
GAME 7
1
3
1
1
2
8
GAME 8
2
2
0
1
2
8
GAME 9
2
1
5
1
8
GAME 10
1
2
0
0
1
8
GAME 11
2
1
5
2
8
GAME 12
2
1
6
1
8
GAME 13
3
0
2
3
3
8
GAME 14
2
1
3
5
3
8
GAME 15
4
2
5
1
8
GAME 16
4
1
3
2
8
GAME 17
4
0...

output:

NRBBNKQR
RBBNQKRN
BBQRNKNR
BBRKNQRN
QRBKNBRN
NRBBNKQR
RBBNQKRN
BBRNNKQR
NRBKQBRN
NRBBNKQR
BNRBNKRQ
BNRBQNKR
BBRNQKRN
NRBKNBRQ
NRBBNKQR
RBBNQKRN
BBQNRKNR
RNBKNBRQ
QRBKNNRB
NRBBNKQR
RBBNQKRN
BBQRNKNR
BBRNKRNQ
BBRKRQNN
NRBKQNRB
NRBBNKQR
BNRBNKRQ
BBNRNKQR
BBRKNQNR
NRBKNQRB
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 657ms
memory: 3552kb

input:

GAME 1
1
1
2
4
4
8
GAME 2
2
3
1
2
2
8
GAME 3
1
2
2
2
1
8
GAME 4
0
3
3
5
8
GAME 5
0
3
2
2
8
GAME 6
0
4
4
4
8
GAME 7
2
4
2
2
8
GAME 8
3
3
0
2
2
8
GAME 9
2
4
3
0
8
GAME 10
1
2
2
1
8
GAME 11
1
1
1
8
GAME 12
2
3
1
0
8
GAME 13
1
2
4
1
8
GAME 14
1
1
4
1
1
8
GAME 15
1
2
4
0
8
GAME 16
0
5
2
0
8
GAME 17
0
4
2...

output:

NRBBNKQR
BRNNKBQR
RKQNRBBN
BBRQKNRN
BBRKQRNN
RBBQKRNN
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRKNQRN
BBRKRQNN
RBBNKRQN
NRBBNKQR
BRNNKBQR
BNRBKRQN
BBNRKQRN
BBRKRNQN
RBBNKRNQ
NRBBNKQR
RKNNRQBB
BQRNKRNB
RBKNBRQN
RBQNKRBN
NRBBNKQR
RKNNRQBB
BQRNKRNB
RKNRBBNQ
RBNQKRBN
NRBBNKQR
RKNNRQBB
RBKNBNRQ
BBNRKRQN
RBNNKRBQ
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 641ms
memory: 3492kb

input:

GAME 1
3
0
3
3
8
GAME 2
4
1
1
4
8
GAME 3
4
1
1
6
8
GAME 4
2
0
1
2
0
8
GAME 5
3
1
1
1
1
8
GAME 6
3
0
1
2
0
8
GAME 7
0
0
6
5
8
GAME 8
1
4
1
5
8
GAME 9
0
1
5
4
8
GAME 10
1
2
6
3
8
GAME 11
2
3
1
3
3
8
GAME 12
1
2
6
4
8
GAME 13
0
2
2
5
8
GAME 14
0
1
6
8
GAME 15
1
4
2
3
8
GAME 16
0
2
1
3
8
GAME 17
1
1
2
5...

output:

NRBBNKQR
RBBNQKRN
BNRBQNKR
BRKBRNNQ
QRNBKNBR
NRBBNKQR
BNRBNKRQ
QBBRKRNN
BRNBKQNR
NRQBKNBR
NRBBNKQR
BNRBNKRQ
QBBRKRNN
BRNBKQNR
NRNBKQBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BBRQKNNR
BBRKRQNN
QRNNKBBR
NRBBNKQR
RBBNQKRN
BRKBRNQN
BNNBRKQR
BBRQKRNN
NRQNKBBR
NRBBNKQR
RBBNQKRN
BNRBQNKR
BBNRKRQN
BBRKRNQN
NRNQKBBR
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 606ms
memory: 3524kb

input:

GAME 1
2
1
0
3
2
8
GAME 2
3
2
3
5
8
GAME 3
4
0
1
1
8
GAME 4
1
3
3
4
8
GAME 5
2
0
0
1
1
8
GAME 6
2
0
0
1
2
8
GAME 7
2
2
2
2
0
8
GAME 8
3
1
0
1
8
GAME 9
4
1
3
1
8
GAME 10
1
4
4
2
8
GAME 11
2
0
0
3
0
8
GAME 12
2
1
1
1
0
8
GAME 13
3
6
1
2
8
GAME 14
2
6
2
2
8
GAME 15
3
6
2
1
8
GAME 16
1
1
4
1
2
8
GAME 17...

output:

NRBBNKQR
RNBBQKRN
NRNKBRQB
BBRKRNNQ
BBRKRNQN
QBBRKNNR
NRBBNKQR
RBBNQKRN
BBQNRKNR
NBBRQNKR
NBBRKQNR
NRBBNKQR
BNRBNKRQ
BRNKQBNR
BBRKRQNN
NBBRKNQR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBNRKRQN
QBNRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNKBRN
BBRKRQNN
NBQRKNBR
NRBBNKQR
RNBBQKRN
BRKQNRNB
BQRNKBRN
BBRKRQNN
NBNRKQBR
NRB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 603ms
memory: 3492kb

input:

GAME 1
3
2
5
4
8
GAME 2
2
2
1
4
4
8
GAME 3
4
4
3
8
GAME 4
4
5
3
8
GAME 5
3
2
4
3
8
GAME 6
5
5
2
8
GAME 7
2
1
1
4
3
8
GAME 8
3
2
4
4
8
GAME 9
4
2
4
3
8
GAME 10
3
3
4
3
2
8
GAME 11
4
3
2
3
8
GAME 12
3
4
5
3
8
GAME 13
3
1
1
4
8
GAME 14
4
3
3
2
8
GAME 15
5
3
1
1
8
GAME 16
4
5
1
8
GAME 17
5
5
3
8
GAME 18...

output:

NRBBNKQR
RBBNQKRN
BBQNRKNR
BBRKRQNN
BBRQNKNR
NRBBNKQR
RNBBQKRN
RKBBRNNQ
BBRQKRNN
BBRKRQNN
BBRNQKNR
NRBBNKQR
BNRBNKRQ
BBRKRNNQ
BBRNNKQR
NRBBNKQR
BNRBNKRQ
BBRKQRNN
BQRBNKNR
NRBBNKQR
RBBNQKRN
BBQNRKNR
BBRQKRNN
BNRBQKNR
NRBBNKQR
BQRBNNKR
NRBBQNKR
BNRBNKQR
NRBBNKQR
RNBBQKRN
NRNKBRQB
BBNQRKNR
BBRKRQNN
QBR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 642ms
memory: 3444kb

input:

GAME 1
2
2
3
2
0
8
GAME 2
2
3
4
4
8
GAME 3
2
3
3
3
0
8
GAME 4
1
4
4
1
8
GAME 5
1
3
6
0
8
GAME 6
1
3
4
0
8
GAME 7
4
3
5
8
GAME 8
3
1
4
4
8
GAME 9
4
3
4
5
8
GAME 10
3
1
2
3
8
GAME 11
3
0
3
2
8
GAME 12
2
1
2
3
8
GAME 13
5
5
6
8
GAME 14
5
4
0
8
GAME 15
6
1
1
8
GAME 16
4
1
2
0
8
GAME 17
5
3
1
0
8
GAME 18...

output:

NRBBNKQR
RNBBQKRN
RKBBRNNQ
BRKBNNRQ
BBRQKRNN
RQNBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
QNRBBKNR
RNQBBNKR
NRBBNKQR
RNBBQKRN
RQKBNNBR
BBRNNQKR
BBRKRNQN
RNNBBQKR
NRBBNKQR
BRNNKBQR
QNBNRBKR
BBNRQKRN
RQNNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBRKRQNN
RNQNBBKR
NRBBNKQR
BRNNKBQR
RBQNBNKR
BBRKRNNQ
RNNQBBKR
NRBBNKQR
BNR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed