QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300717 | #7863. Parity Game | willow# | TL | 1ms | 3904kb | C++17 | 2.9kb | 2024-01-08 17:40:40 | 2024-01-08 17:40:41 |
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);
Op(pos, c);
fflush(stdout);
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 + 1] == 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;
for(int i = pre + 1; i <= n; ) {
assert(a[i] == 0);
if(pre % 2 == 0) {
pos = i;
break;
}
int j = i + 1;
assert(j > n || a[j] == 1);
while(j <= n && a[j] == 1)
++ j;
if((j - i - 1) % 2 == 0) {
pos = i;
break;
}
pre = j - i - 1, i = j;
}
if(pos == -1) {
Out(1, '*');
continue;
}
if(pos == n) {
Out(pos - 1, '+');
continue;
}
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: 3868kb
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: 3904kb
input:
4 0 1 0 1 0 1 + 1
output:
Alice 1 * 1 *
result:
ok The player wins!
Test #3:
score: -100
Time Limit Exceeded
input:
5 1 1 1 1 0 0