QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300727 | #7863. Parity Game | willow# | WA | 1ms | 3800kb | C++17 | 2.8kb | 2024-01-08 17:59:42 | 2024-01-08 17:59:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, t, a[maxn];
void Op(int pos, char c) {
if(c == '+')
a[pos] = a[pos] ^ a[pos + 1];
if(c == '*')
a[pos] = a[pos] * a[pos + 1];
for(int i = pos + 1; i < n; ++ i)
a[i] = a[i + 1];
-- n;
// cerr << n << endl;
// for(int i = 1; i <= n; ++ i)
// cerr << a[i] << " ";
// cerr << endl;
}
void Step() {
// cerr << "!" << endl;
int pos;
char op[2];
scanf("%d %s", &pos, op);
Op(pos, op[0]);
}
void Out(int pos, char c) {
printf("%d %c\n", pos, c);
fflush(stdout);
Op(pos, c);
if(n > 1)
Step();
}
int main() {
scanf("%d%d", &n, &t);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
int ok = 0;
if(t == 0 && n % 2 == 0) {
puts("Alice");
ok = 1;
}
if(t == 1 && n % 2 == 1) {
puts("Bob");
ok = 1;
Step();
}
if(ok) {
while(n > 2)
Out(1, '*');
if((a[1] + a[2]) % 2 == 0)
Out(1, '+');
else
Out(1, '*');
return 0;
}
int cnt[2] = {0, 0};
for(int i = 1; i <= n; ) {
int j = i;
while(j <= n && a[i] == a[j]) {
++ j;
}
if(a[i] == 1) {
cnt[1] += (j - i) % 2;
}
else {
cnt[a[i]] += j - i;
}
i = j;
}
int flg = -1;
//cerr << cnt[0] <<' ' << cnt[1] << endl;
if(t == 0) {
if(cnt[0] > cnt[1]) {
puts("Alice");
flg = 0;
}
else {
puts("Bob");
flg = 1;
Step();
}
}
if(t == 1) {
if(cnt[1] >= cnt[0]) {
puts("Alice");
flg = 1;
}
else {
puts("Bob");
flg = 0;
Step();
}
}
while(n > 1) {
// cerr << "? " << flg << endl;
if(!flg) {
int pos = -1;
for(int i = 1; i < n; ++ i) {
if(a[i] == 1 && a[i + 1] == 1) {
if(i > 1 && a[i - 1] == 0) {
pos = i;
break;
}
if((i + 1 < n && a[i + 2] == 0)) {
pos = i;
break;
}
}
}
if(pos != -1) {
Out(pos, '+');
continue;
}
for(int i = 1; i < n; ++ i) {
if((a[i] == 1 && a[i + 1] == 0) || (a[i] == 0 && a[i + 1] == 1)) {
pos = i;
break;
}
}
// assert(pos != -1);
if(pos == -1)
pos = 1;
Out(pos, '+');
}
else {
int pos = -1;
for(int i = 1; i < n; ++ i) {
if(a[i] == 0 && a[i + 1] == 0) {
pos = i;
break;
}
}
if(pos != -1) {
Out(pos, '+');
continue;
}
int pre = 1;
while(pre <= n && a[pre] == 1)
++ pre;
-- pre;
if(pre == n) {
Out(1, '*');
continue;
}
if(pre % 2 == 0) {
Out(pre, '+');
continue;
}
for(int i = n; i >= 1; -- i) {
if(a[i] == 0) {
pos = i; break;
}
}
Out(pos - 1, '+');
}
}
assert(n == 1);
assert(a[1] == flg);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3800kb
input:
4 1 0 1 0 1 0 +
output:
Alice 0 + 0 +
result:
wrong answer invalid operation