QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301537#7863. Parity GamefxhdWA 1ms3776kbC++172.1kb2024-01-10 02:15:122024-01-10 02:15:13

Judging History

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

  • [2024-01-10 02:15:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3776kb
  • [2024-01-10 02:15:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "debug.hpp"
#else
  #define dbg(...) 0
#endif

pair<int, bool> get_winning_move(const vector<bool>& a, int t) {
  int n = a.size();
  const pair<int, bool> LOSE{-1, false};
  if ((n & 1) == (t & 1)) {
    if (n & 1) return LOSE;
    return {0, !a[0] || !a[1]};
  }
  if (n & 1) {
    for (int i = 0; i < n; i += 2) if (!a[i]) {
      if (i == 0) {
        return {n - 2, !a[n - 2] || !a[n - 1]};
      }
      return {0, !a[0] || !a[1]};
    }
    return LOSE;
  }
  int l = -2;
  while (((l + 2) < n) && a[l + 2]) l += 2;
  int r = n + 1;
  while (((r - 2) >= 0) && a[r - 2]) r -= 2;
  if (r > (l + 3)) return LOSE;
  if (l == (n - 2)) {
    return {n - 2, a[n - 2] && a[n - 1]};
  }
  return {l + 2, a[l + 2] && a[l + 3]};  
}

void print_move(pair<int, bool> m) {
  cout << (m.first + 1) << ' ' << (m.second ? '*' : '+') << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, t;
  cin >> n >> t;
  vector<bool> a(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a[i] = x;
  }
  auto apply_move = [&](int p, bool is_mult) -> void {
    vector<bool> b(n - 1);
    for (int i = 0; i < p; ++i) {
      b[i] = a[i];
    }
    if (is_mult) {
      b[p] = a[p] & a[p + 1];
    }
    else {
      b[p] = a[p] ^ a[p + 1];
    }
    for (int i = p + 2; i < n; ++i) {
      b[i - 1] = a[i];
    }
    b.swap(a);
    n--;
  };
  if (pair<int, bool> winning_move = get_winning_move(a, t); winning_move.first >= 0) {
    cout << "Alice" << endl;
    print_move(winning_move);
    apply_move(winning_move.first, winning_move.second);
  }
  else {
    cout << "Bob" << endl;
  }
  while (n > 1) {
    int p;
    string s;
    cin >> p >> s;
    assert(int(s.size()) == 1);
    assert((s[0] == '*') || (s[0] == '+'));
    apply_move(p - 1, s[0] == '*');
    if (n > 1) {
      pair<int, bool> winning_move = get_winning_move(a, t);
      assert(winning_move.first >= 0);
      print_move(winning_move);
      apply_move(winning_move.first, winning_move.second);
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3500kb

input:

4 1
0 1 0 1
1 *
1

output:

Alice
1 +
1 +

result:

ok The player wins!

Test #2:

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

input:

4 0
1 0 1 0
1 +
1

output:

Alice
1 *
1 *

result:

ok The player wins!

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3776kb

input:

5 1
1 1 1 0 0
4 +
1 *
0

output:

Bob
3 +
1 *

result:

wrong answer The interactor wins!