QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301537 | #7863. Parity Game | fxhd | WA | 1ms | 3776kb | C++17 | 2.1kb | 2024-01-10 02:15:12 | 2024-01-10 02:15:13 |
Judging History
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!