QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238779#7635. Fairy Chessucup-team859#AC ✓481ms3532kbC++143.8kb2023-11-04 17:30:212023-11-04 17:30:21

Judging History

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

  • [2023-11-04 17:30:21]
  • 评测
  • 测评结果:AC
  • 用时:481ms
  • 内存:3532kb
  • [2023-11-04 17:30:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

inline bool is_knight(char ch) {
  return ch == 'A' || ch == 'C' || ch == 'M';
}

inline bool is_bishop(char ch) {
  return ch == 'A' || ch == 'B' || ch == 'M' || ch == 'Q';
}

inline bool is_rook(char ch) {
  return ch == 'R' || ch == 'M' || ch == 'Q' || ch == 'C';
}

const int dx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
const int dy[] = {-2, 2, -2, 2, -1, 1, -1, 1};

string s;
int cs;
int p[8][8];
int f[8][8];

inline bool in_bounds(int i, int j) {
  return i >= 0 && j >= 0 && i < 8 && j < 8;
}

inline void mark_knight(int i, int j, int sgn) {
  for (int k = 0; k < 8; ++k) {
    int x = dx[k] + i;
    int y = dy[k] + j;
    if (in_bounds(x, y))
      f[x][y] += sgn, cs |= p[x][y];
  }
}

inline void mark_bishop(int i, int j, int sgn) {
  for (int s1 = -1; s1 <= 1; s1 += 2) {
    for (int s2 = -1; s2 <= 1; s2 += 2) {
      for (int k = 1; k < 8; ++k) {
        int x = k * s1 + i;
        int y = k * s2 + j;
        if (in_bounds(x, y))
          f[x][y] += sgn, cs |= p[x][y];
        else
          break;
      }
    }
  }
}

inline void mark_rook(int i, int j, int sgn) {
  for (int s1 = -1; s1 <= 1; s1 += 2) {
    for (int k = 1; k < 8; ++k) {
      int x = k * s1 + i;
      int y = j;
      if (in_bounds(x, y))
        f[x][y] += sgn, cs |= p[x][y];
      else
        break;
    }
    for (int k = 1; k < 8; ++k) {
      int x = i;
      int y = k * s1 + j;
      if (in_bounds(x, y))
        f[x][y] += sgn, cs |= p[x][y];
      else
        break;
    }
  }
}

void mark_pos(int i, int j, char ch, int sgn) {
  f[i][j] += sgn;
  if (is_knight(ch))
    mark_knight(i, j, sgn);
  if (is_bishop(ch))
    mark_bishop(i, j, sgn);
  if (is_rook(ch))
    mark_rook(i, j, sgn);
}

string dum = "PLM";

int back(int pos = 0) {
  if (pos == 12) {
    return 0;
  }

  int res = 0;
  int l = 8;
  if (pos == 0)
    l = 4;

  for (int i = 0; i < l; ++i) {
    for (int j = 0; j < l; ++j) {
      if (!f[i][j]) {
        cs = false;
        mark_pos(i, j, s[pos], 1);
        p[i][j] = 1;

        if (!cs)
          res = !back(pos + 1);

        p[i][j] = 0;
        mark_pos(i, j, s[pos], -1);
        if (res) {
          //if (pos <= 5)
          //  debug("WIN", pos);
          return 1;
        }
      }
    }
  }

  //if (pos <= 5)
  //  debug("LOSE", pos);

  return 0;
}

void solve() {
  int n;
  cin >> s;
  cout << ((back() == 0) ? "Bob" : "Alice") << '\n';
}

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

  int t = 1;
//  cin >> t;
  while (t--)
    solve();

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 38ms
memory: 3496kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 8ms
memory: 3516kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 11ms
memory: 3488kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 13ms
memory: 3528kb

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 7ms
memory: 3400kb

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

score: 0
Accepted
time: 6ms
memory: 3468kb

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3476kb

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

score: 0
Accepted
time: 11ms
memory: 3464kb

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 37ms
memory: 3516kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 10ms
memory: 3496kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

score: 0
Accepted
time: 6ms
memory: 3496kb

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 18ms
memory: 3400kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 7ms
memory: 3400kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 28ms
memory: 3496kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 10ms
memory: 3480kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 36ms
memory: 3520kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 8ms
memory: 3408kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3404kb

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 10ms
memory: 3468kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

score: 0
Accepted
time: 4ms
memory: 3416kb

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

score: 0
Accepted
time: 4ms
memory: 3412kb

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 8ms
memory: 3408kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 3ms
memory: 3532kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

score: 0
Accepted
time: 8ms
memory: 3480kb

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

score: 0
Accepted
time: 3ms
memory: 3500kb

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

score: 0
Accepted
time: 3ms
memory: 3464kb

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

score: 0
Accepted
time: 3ms
memory: 3460kb

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 54ms
memory: 3468kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 481ms
memory: 3400kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 63ms
memory: 3500kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 74ms
memory: 3464kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 39ms
memory: 3408kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 137ms
memory: 3496kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 43ms
memory: 3488kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 351ms
memory: 3464kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 193ms
memory: 3504kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed