QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#230289#7635. Fairy Chessucup-team1191#Compile Error//C++235.1kb2023-10-28 18:00:282023-10-28 18:01:34

Judging History

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

  • [2023-10-28 18:01:34]
  • 评测
  • [2023-10-28 18:00:28]
  • 提交

answer

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

enum class Piece {
  BISHOP,
  ROOK,
  QUEEN,
  ARCHBISHOP,
  CHANCELLOR,
  MAHARAJAH,
  KNIGHT,
};

const int N = 8;
const int K = 6;

ull mask_cover[N][N][K + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  auto valid = [&](int x, int y) { return 0 <= x && x < N && 0 <= y && y < N; };

  auto add = [&](int i, int j, int x, int y, Piece k) {
    if (valid(x, y)) {
      mask_cover[i][j][(int)k] |= 1ULL << (x * N + y);
    }
  };

  { // knight
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        add(i, j, i, j, Piece::KNIGHT);
        add(i, j, i + 1, j + 2, Piece::KNIGHT);
        add(i, j, i + 1, j - 2, Piece::KNIGHT);
        add(i, j, i - 1, j + 2, Piece::KNIGHT);
        add(i, j, i - 1, j - 2, Piece::KNIGHT);
        add(i, j, i + 2, j + 1, Piece::KNIGHT);
        add(i, j, i + 2, j - 1, Piece::KNIGHT);
        add(i, j, i - 2, j + 1, Piece::KNIGHT);
        add(i, j, i - 2, j - 1, Piece::KNIGHT);
      }
    }
  }

  { // bishop
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int t = 0; t < 3 * N; ++t) {
          add(i, j, i + t, j + t, Piece::BISHOP);
          add(i, j, i + t, j - t, Piece::BISHOP);
          add(i, j, i - t, j + t, Piece::BISHOP);
          add(i, j, i - t, j - t, Piece::BISHOP);
        }
      }
    }
  }

  { // rook
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int t = 0; t < 3 * N; ++t) {
          add(i, j, i + t, j, Piece::ROOK);
          add(i, j, i - t, j, Piece::ROOK);
          add(i, j, i, j + t, Piece::ROOK);
          add(i, j, i, j - t, Piece::ROOK);
        }
      }
    }
  }

  { // queen
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::QUEEN] =
            mask_cover[i][j][(int)Piece::BISHOP] |
            mask_cover[i][j][(int)Piece::ROOK];
      }
    }
  }

  { // archibishop
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::ARCHBISHOP] =
            mask_cover[i][j][(int)Piece::BISHOP] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  { // chancellor
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::CHANCELLOR] =
            mask_cover[i][j][(int)Piece::ROOK] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  { // maharajah
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::MAHARAJAH] =
            mask_cover[i][j][(int)Piece::QUEEN] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  vector<int> order(2 * K);
  for (int i = 0; i < 2 * K; ++i) {
    char c;
    cin >> c;
    if (c == 'B') {
      order[i] = (int)Piece::BISHOP;
    } else if (c == 'R') {
      order[i] = (int)Piece::ROOK;
    } else if (c == 'Q') {
      order[i] = (int)Piece::QUEEN;
    } else if (c == 'A') {
      order[i] = (int)Piece::ARCHBISHOP;
    } else if (c == 'C') {
      order[i] = (int)Piece::CHANCELLOR;
    } else if (c == 'M') {
      order[i] = (int)Piece::MAHARAJAH;
    } else {
      assert(false);
    }
  }

  /*for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      cout << ((mask_cover[3][3][(int)Piece::MAHARAJAH] >> (N * i + j)) & 1);
    }
    cout << '\n';
  }
  return 0;*/
  mt19937_64 rnd(123);

  ull mask_pieces = 0;
  ull mask_covered = 0;

  int ptr = 0;

  map<pair<ull, ull>, bool> mem;
  function<bool()> rec = [&]() {
    auto hash_pos = make_tuple(mask_covered, mask_pieces);

    if (mem.count(hash_pos)) {
      return mem[hash_pos];
    }

    if (ptr == 2 * K) {
      mem[hash_pos] = false;
      return false;
    }

    ull mask_covered_anti = ~mask_covered;

    while (mask_covered_anti > 0) {
      int b = __builtin_ctzll(mask_covered_anti);
      mask_covered_anti &= ~(1ULL << b);
      int i = b / N;
      int j = b % N;

      int p = order[ptr];

      if (mask_pieces & mask_cover[i][j][p]) {
        continue;
      }

      ull sf_covered = mask_covered;
      mask_pieces |= (1ULL << (i * N + j));
      mask_covered |= mask_cover[i][j][p];
      ++ptr;

      auto res = rec();

      --ptr;
      mask_pieces &= ~(1ULL << (i * N + j));
      mask_covered = sf_covered;

      if (!res) {
        mem[hash_pos] = true;
        return true;
      }
    }
    mem[hash_pos] = false;
    return false;
  };
  cout << (rec() ? "Alice" : "Bob") << '\n';
}

詳細信息

answer.code: In lambda function:
answer.code:174:18: error: no matching function for call to ‘std::map<std::pair<long long unsigned int, long long unsigned int>, bool>::count(std::tuple<long long unsigned int, long long unsigned int>&)’
  174 |     if (mem.count(hash_pos)) {
      |         ~~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/11/map:61,
                 from answer.code:12:
/usr/include/c++/11/bits/stl_map.h:1221:9: note: candidate: ‘template<class _Kt> decltype (((const std::map<_Key, _Tp, _Compare, _Alloc>*)this)->std::map<_Key, _Tp, _Compare, _Alloc>::_M_t._M_count_tr(__x)) std::map<_Key, _Tp, _Compare, _Alloc>::count(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<long long unsigned int, long long unsigned int>; _Tp = bool; _Compare = std::less<std::pair<long long unsigned int, long long unsigned int> >; _Alloc = std::allocator<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> >]’
 1221 |         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
      |         ^~~~~
/usr/include/c++/11/bits/stl_map.h:1221:9: note:   template argument deduction/substitution failed:
/usr/include/c++/11/bits/stl_map.h: In substitution of ‘template<class _Kt> decltype (((const std::map<std::pair<long long unsigned int, long long unsigned int>, bool>*)this)->std::map<std::pair<long long unsigned int, long long unsigned int>, bool>::_M_t.std::_Rb_tree<std::pair<long long unsigned int, long long unsigned int>, std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool>, std::_Select1st<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> >, std::less<std::pair<long long unsigned int, long long unsigned int> >, std::allocator<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> > >::_M_count_tr<_Kt, _Req>(__x)) std::map<std::pair<long long unsigned int, long long unsigned int>, bool>::count<_Kt>(const _Kt&) const [with _Kt = std::tuple<long long unsigned int, long long unsigned int>]’:
answer.code:174:18:   required from here
/usr/include/c++/11/bits/stl_map.h:1221:65: error: no matching function for call to ‘std::_Rb_tree<std::pair<long long unsigned int, long long unsigned int>, std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool>, std::_Select1st<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> >, std::less<std::pair<long long unsigned int, long long unsigned int> >, std::allocator<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> > >::_M_count_tr(const std::tuple<long long unsigned int, long long unsigned int>&) const’
 1221 |         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
      |                                                 ~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/11/map:60,
                 from answer.code:12:
/usr/include/c++/11/bits/stl_tree.h:1314:9: note: candidate: ‘template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_count_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = std::pair<long long unsigned int, long long unsigned int>; _Val = std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool>; _KeyOfValue = std::_Select1st<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> >; _Compare = std::less<std::pair<long long unsigned int, long long unsigned int> >; _Alloc = std::allocator<std::pair<const std::pair<long long unsigned int, long long unsigned int>, bool> >]’
 1314 |         _M_count_tr(const _Kt& __k) const
      |         ^~~~~~~~~~~
/usr/include/c++/11/bits/stl_tree.h:1314:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/string:48,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/streambuf:41,
                 from /usr/include/c++/11/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/11/iterator:66,
                 from /usr/include/c++/11/bits/ranges_algobase.h:36,
                 from /usr/include/c++/11/bits/ranges_algo.h:35,
                 from /usr/include/c++/11/algorithm:64,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_function.h: In substitution of ‘template<class _Func, class _SfinaeType> using __has_is_transparent_t = typename std::__has_is_transparent<_Func, _SfinaeType>::type [with _Func = std::less<std::pair<long long unsigned int, long long unsigned int> >; _SfinaeType = std::tuple<long long unsigned int, long long unsigned int>]’:
/usr/include/c++/11/bits/stl_tree.h:1312:9:   required by substitution of ‘template<class _Kt> decltype (((const std::map<std::pair<long long unsigned int, long long unsigned int>, bool>*)this)->std::ma...