QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #605851 | #7863. Parity Game | ucup-team4906 | TL | 0ms | 0kb | C++14 | 13.1kb | 2024-10-02 20:04:43 | 2024-10-02 20:04:44 |
answer
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
void solve()
{
int n, t;
cin >> n >> t;
vi a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
int sz = n;
auto opt = [&](int p, char op)
{
vi res(n + 2);
sz--;
for (int i = 1; i < p; i++)
res[i] = a[i];
if (op == '+') res[p] = (a[p] + a[p + 1]) % 2;
else res[p] = a[p] * a[p + 1];
for (int i = p + 2; i <= n; i++)
res[i - 1] = a[i];
a = res;
};
auto get0 = [&](int x)
{
if (a[x] == 0 || a[x + 1] == 0)
{
cout << x << " *";
cout << endl;
opt(x, '*');
}
else
{
cout << x << " +";
cout << endl;
opt(x, '+');
}
};
auto get1 = [&](int x)
{
if (a[x] & a[x + 1])
{
cout << x << " *";
cout << endl;
opt(x, '*');
}
else
{
cout << x << " +";
cout << endl;
opt(x, '+');
}
};
if ((t == 0 && (n & 1 ^ 1)))
{
cout << "Alice";
cout << endl;
for (int i = 1; i < n / 2; i++)
{
opt(1, '+');
cout << 1 << " +";
cout << endl;
int p;
char op;
cin >> p >> op;
opt(p, op);
}
if (a[1] == 0 || a[2] == 0)
cout << 1 << " *";
else
cout << 1 << " +";
cout << endl;
}
else if ((t == 1 && (n & 1)))
{
cout << "Bob";
cout << endl;
for (int i = 1; i <= n / 2; i++)
{
int p;
char op;
cin >> p >> op;
opt(p, op);
if (i == n / 2)
{
if (a[1] == 0 || a[2] == 0)
cout << 1 << " *";
else
cout << 1 << " +";
cout << endl;
}
else
{
opt(1, '+');
cout << 1 << " +";
cout << endl;
}
}
}
else if (t == 0 && n & 1)
{
int p = 0;
int mark = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
int now = i - 1 - p;
if ((now & 1 ^ 1) && !(now == 0 && p == -1))
{
mark = 1;
}
p = i;
}
}
int now = n - p;
if (now & 1 ^ 1)
mark = 1;
if (a[1] == 0 || a[n] == 0)
mark = 1;
if (mark)
{
cout << "Alice";
cout << endl;
for (int i = 1; i <= n / 2; i++)
{
if (a[1] == 0)
{
get0(2);
}
else if (a[sz] == 0)
{
get0(sz - 2);
}
else
{
int p = -1;
for (int i = 1; i <= sz; i++)
{
if (a[i] == 0)
{
int now = i - 1 - p;
if ((now & 1 ^ 1) && !(now == 0 && p == -1))
{
// p + 1, i - 1;
if (now == 0)
{
// i - 1, i
if (i - 1 >= 3)
{
get0(i - 3);
}
else
{
get0(i + 1);
}
}
else
{
get0(i - 1);
}
break;
}
p = i;
}
}
}
int p;
char op;
cin >> p >> op;
opt(p, op);
}
}
else
{
cout << "Bob";
cout << endl;
for (int i = 1; i <= n / 2; i++)
{
int p;
char op;
cin >> p >> op;
opt(p, op);
if (a[1] == 0)
{
get1(1);
}
else if (a[sz] == 0)
get1(sz - 1);
else
{
int mark = 0;
for (int j = 1; j < sz; j++)
{
if (a[j] == 0 && a[j + 1] == 0)
{
if (j > 1)
{
assert(a[j - 1] == 1);
get1(j - 1);
}
else
{
assert(a[j + 2] == 1);
get1(j + 1);
}
mark = 1;
break;
}
}
if (!mark)
{
int flag = 0;
for (int i = 1; i <= sz; i++)
if (a[i] == 0)
{
if (i > 1)
get1(i - 1);
else
get1(i);
flag = 1;
break;
}
if (!flag)
get1(1);
}
}
}
}
}
else
{
if (n == 2)
{
if (a[1] == 1 || a[2] == 1)
{
cout << "Alice";
cout << endl;
if (a[1] == 0 || a[2] == 0)
{
cout << 1 << " +";
cout << endl;
}
else
{
cout << 1 << " *";
cout << endl;
}
}
else
{
cout << "Bob\n";
cout << endl;
int p;
char op;
cin >> p >> op;
}
return;
}
int ans = 0;
for (int ch = 0; ch <= 1 && !ans; ch++)
for (int pos = 1; pos < n && !ans; pos++)
{
char op = ((ch == 0) ? '+' : '*');
vi res(n + 2);
sz--;
for (int i = 1; i < pos; i++)
res[i] = a[i];
if (op == '+') res[pos] = (a[pos] + a[pos + 1]) % 2;
else res[pos] = a[pos] * a[pos + 1];
for (int i = pos + 2; i <= n; i++)
res[i - 1] = a[i];
int p = -1;
int mark = 0;
for (int i = 1; i <= sz; i++)
{
if (res[i] == 0)
{
int now = i - 1 - p;
if ((now & 1 ^ 1) && !(now == 0 && p == -1))
{
mark = 1;
}
p = i;
}
}
int now = sz - p;
if (now & 1 ^ 1)
mark = 1;
if (res[1] == 0 || res[sz] == 0)
mark = 1;
// if (pos == 1 && op == '+')
// {
// for (int i = 1; i <= sz; i++)
// cerr << res[i] << " \n"[i == sz];
// cerr << mark << "\n";
// }
if (mark == 0)
{
cout << "Alice";
cout << endl;
cout << pos << " " << op;
cout << endl;
a = res;
for (int i = 1; i <= n / 2 - 1; i++)
{
int p;
char op;
cin >> p >> op;
opt(p, op);
if (a[1] == 0)
{
get1(1);
}
else if (a[sz] == 0)
get1(sz - 1);
else
{
int mark = 0;
for (int j = 1; j < sz; j++)
{
if (a[j] == 0 && a[j + 1] == 0)
{
if (j > 1)
{
assert(a[j - 1] == 1);
get1(j - 1);
}
else
{
assert(a[j + 2] == 1);
get1(j + 1);
}
mark = 1;
break;
}
}
if (!mark)
{
int flag = 0;
for (int i = 1; i <= sz; i++)
if (a[i] == 0)
{
if (i > 1)
get1(i - 1);
else
get1(i);
flag = 1;
break;
}
if (!flag)
get1(1);
}
}
}
ans = 1;
}
sz++;
}
if (!ans)
{
assert(sz == n);
cout << "Bob";
cout << endl;
int p;
char op;
cin >> p >> op;
opt(p, op);
for (int i = 1; i <= n / 2 - 1; i++)
{
if (a[1] == 0)
{
get0(2);
}
else if (a[sz] == 0)
{
get0(sz - 2);
}
else
{
int p = 0;
for (int i = 1; i <= sz; i++)
{
if (a[i] == 0)
{
int now = i - 1 - p;
if ((now & 1 ^ 1) && !(now == 0 && p == -1))
{
// p + 1, i - 1;
if (now == 0)
{
// i - 1, i
if (i - 1 >= 3)
{
get0(i - 3);
}
else
{
get0(i + 1);
}
}
else
{
get0(i - 1);
}
break;
}
p = i;
}
}
}
int p;
char op;
cin >> p >> op;
opt(p, op);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 1 0 1 0 1 1 +
output:
Bob