QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355504 | #7863. Parity Game | ucup-team1191# | WA | 2ms | 3844kb | C++23 | 3.5kb | 2024-03-16 18:44:26 | 2024-03-16 18:44:28 |
Judging History
answer
#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>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, t;
cin >> n >> t;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int last = n % 2;
auto make = [&](int x, int y, int z) {
// 0 - sum, 1 - mult, -1 - impossible
if (z == 0) {
if (x == 0 || y == 0) {
return 1;
} else {
return 0;
}
} else {
if (x == 1 && y == 1) {
return 1;
} else if (x == 1 || y == 1) {
return 0;
} else {
return -1;
}
}
};
auto make_op = [&](int p, int op) {
int x;
if (op == 0) {
x = (a[p] + a[p + 1]) % 2;
} else {
x = a[p] * a[p + 1];
}
a.erase(a.begin() + p);
a.erase(a.begin() + p);
a.insert(a.begin() + p, x);
};
auto check_good = [&](const vector<int> &a) {
assert(a.size() % 2 == 1);
for (int i = 0; i < (int)a.size(); i += 2) {
if (a[i] == 0) {
return 1;
}
}
return 0;
};
if (last == t) {
int play = last;
cout << (play == 0 ? "Alice" : "Bob") << endl;
for (int turn = 0; turn < n - 1; ++turn) {
if (turn % 2 == play) {
int op = make(a[0], a[1], 0);
cout << 1 << ' ' << (op == 0 ? "+" : "*") << endl;
make_op(0, op);
} else {
int p; char c;
cin >> p >> c;
--p;
make_op(p, (c == '+' ? 0 : 1));
}
}
} else {
bool want_nlast = false;
if (n % 2 == 1) {
if (check_good(a)) {
want_nlast = true;
}
} else {
want_nlast = true;
for (int i = 0; i + 1 < n; ++i) {
for (int op = 0; op <= 1; ++op) {
vector<int> sf = a;
make_op(i, op);
if (!check_good(a)) {
want_nlast = false;
}
a = sf;
}
}
}
int play;
if (want_nlast) {
play = last ^ 1;
} else {
play = last;
}
cout << (play == 0 ? "Alice" : "Bob") << endl;
for (int turn = 0; turn < n - 1; ++turn) {
if (turn % 2 == play) {
if (want_nlast) {
int idx;
if (a[0] != 0) {
idx = 0;
} else {
idx = (int)a.size() - 2;
}
int op = make(a[idx], a[idx], 0);
cout << idx + 1 << ' ' << (op == 0 ? "+" : "*") << endl;
make_op(idx, op);
} else {
int idx = -1, go_op = -1;
for (int i = 0; i + 1 < (int)a.size(); ++i) {
for (int op = 0; op <= 1; ++op) {
vector<int> sf = a;
make_op(i, op);
if (!check_good(a)) {
idx = i, go_op = op;
break;
}
a = sf;
}
if (idx != -1) {
break;
}
}
assert(idx != -1);
cout << idx + 1 << ' ' << (go_op == 0 ? "+" : "*") << endl;
}
} else {
int p; char c;
cin >> p >> c;
--p;
make_op(p, (c == '+' ? 0 : 1));
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
4 1 0 1 0 1 1 * 1
output:
Alice 1 + 1 +
result:
ok The player wins!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 0 1 0 1 0 1 + 1
output:
Alice 1 * 1 *
result:
ok The player wins!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
5 1 1 1 1 0 0 4 + 1 + 1
output:
Bob 1 + 1 *
result:
ok The player wins!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 1 1 0 1 1 * 1
output:
Bob 1 *
result:
ok The player wins!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 0 1 0 1 1 * 1
output:
Bob 1 +
result:
ok The player wins!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 1 0 1 1
output:
Alice 1 +
result:
ok The player wins!
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 3600kb
input:
499 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 ...
output:
Alice 498 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + ...
result:
wrong answer The interactor wins!