QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300732 | #7863. Parity Game | willow | RE | 1ms | 3872kb | C++17 | 3.1kb | 2024-01-08 18:05:53 | 2024-01-08 18:05:54 |
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");
fflush(stdout);
ok = 1;
}
if(t == 1 && n % 2 == 1) {
puts("Bob");
fflush(stdout);
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");
fflush(stdout);
flg = 0;
}
else {
puts("Bob");
fflush(stdout);
flg = 1;
Step();
}
}
if(t == 1) {
if(cnt[1] >= cnt[0]) {
puts("Alice");
fflush(stdout);
flg = 1;
}
else {
puts("Bob");fflush(stdout);
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) {
if(!pre)
Out(pre + 1, '+');
else Out(pre, '+');
continue;
}
for(int i = n; i >= 1; -- i) {
if(a[i] == 0) {
pos = i; break;
}
}
if(pos == n)
Out(pos - 1, '+');
else Out(pos, '+');
}
}
assert(n == 1);
assert(a[1] == flg);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
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: 3864kb
input:
4 0 1 0 1 0 1 + 1
output:
Alice 1 * 1 *
result:
ok The player wins!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3620kb
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: 3688kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
3 1 1 0 1 1 * 1
output:
Bob 1 *
result:
ok The player wins!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 0 1 0 1 1 * 1
output:
Bob 1 +
result:
ok The player wins!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 1 0 1 1
output:
Alice 1 +
result:
ok The player wins!
Test #8:
score: -100
Runtime Error
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 2 + 2 + 2 + 4 + 6 + 10 + 12 + 12 + 14 + 14 + 16 + 20 + 20 + 20 + 20 + 22 + 22 + 24 + 24 + 26 + 26 + 26 + 28 + 28 + 28 + 28 + 30 + 30 + 30 + 32 + 32 + 34 + 36 + 38 + 40 + 40 + 48 + 48 + 48 + 48 + 48 + 52 + 54 + 54 + 54 + 58 + 58 + 58 + 60 + 60 + 62 + 66 + 68 + 70 + 70 + 72 + 74 + 76 + 76 + 78 +...