QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289406 | #7863. Parity Game | ucup-team1055# | TL | 1ms | 3848kb | C++20 | 4.0kb | 2023-12-23 17:31:27 | 2023-12-23 17:31:27 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<class T>
bool chmin(T &a, T b) {
if(a <= b) return false;
a = b;
return true;
}
template<class T>
bool chmax(T &a, T b) {
if(a >= b) return false;
a = b;
return true;
}
using namespace std;
vector<int> process(vector<int> v, int i, char c){
int x = v[i];
int y = v[i+1];
int z = (c == '+' ? (x^y) : (x&y));
v.erase(v.begin()+i,v.begin()+i+2);
v.insert(v.begin()+i,z);
return v;
}
char which(int x, int y, int z){
if (z == 0){
if (x == 0 || y == 0) return '*';
else return '+';
}
else {
assert(x != 0 || y != 0);
if (x == 0 || y == 0) return '+';
else return '*';
}
}
bool is_lose_pattern(vector<int> a){
int n = a.size();
assert(n % 2 == 1);
rep(i,0,n){
if (i % 2 == 0 && a[i] != 1){
return false;
}
}
return true;
}
pair<int,char> can_move_to_lose(vector<int> a){
int n = a.size();
int p = -1;
char c = '?';
rep(i,0,n-1){
auto na = process(a,i,'+');
if (is_lose_pattern(na)){
p = i, c = '+';
}
auto ma = process(a,i,'*');
if (is_lose_pattern(ma)){
p = i, c = '*';
}
}
return make_pair(p,c);
}
pair<int,char> strategy(vector<int> a){
int n = a.size();
int p = -1;
char c = '?';
rep(i,0,n-1){
auto na = process(a,i,'+');
if (can_move_to_lose(na).first == -1){
p = i, c = '+';
}
auto ma = process(a,i,'*');
if (can_move_to_lose(ma).first == -1){
p = i, c = '*';
}
}
return make_pair(p,c);
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int n, t; cin >> n >> t;
vector<int> a(n);
rep(i,0,n) cin >> a[i];
auto ask = [&](int p, char c){
cout << p+1 << ' ' << c << endl;
a = process(a,p,c);
n--;
};
auto hear = [&](){
int p; cin >> p; p--;
char c; cin >> c;
a = process(a,p,c);
n--;
};
if (n % 2 == 0 && t == 0){
cout << "Alice" << endl;
while (n > 2){
ask(0,'+');
hear();
}
ask(0,which(a[0],a[1],0));
return 0;
}
if (n % 2 == 1 && t == 1){
cout << "Bob" << endl;
hear();
while (n > 2){
ask(0,'+');
hear();
}
ask(0,which(a[0],a[1],0));
return 0;
}
if (n % 2 == 1){
if (is_lose_pattern(a)){
cout << "Bob" << endl;
while (n > 1){
hear();
auto [p, c] = can_move_to_lose(a);
assert(p != -1);
ask(p,c);
}
return 0;
}
else {
cout << "Alice" << endl;
while (n > 1){
auto [p, c] = strategy(a);
assert(p != -1);
ask(p,c);
hear();
}
return 0;
}
}
else {
auto [ip, ic] = can_move_to_lose(a);
if (ip != -1){
cout << "Alice" << endl;
ask(ip,ic);
while (n > 1){
hear();
auto [p, c] = can_move_to_lose(a);
assert(p != -1);
ask(p,c);
}
return 0;
}
else {
cout << "Bob" << endl;
hear();
while (n > 1){
auto [p, c] = strategy(a);
assert(p != -1);
ask(p,c);
hear();
}
return 0;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3512kb
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: 3848kb
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: 3644kb
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: 1ms
memory: 3596kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 1 1 0 1 1 * 1
output:
Bob 1 *
result:
ok The player wins!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 0 1 0 1 1 * 1
output:
Bob 1 +
result:
ok The player wins!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
2 1 0 1 1
output:
Alice 1 +
result:
ok The player wins!
Test #8:
score: -100
Time Limit Exceeded
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 * 496 * 493 + 491 * 489 + 487 * 485 * 483 + 481 + 479 * 477 + 475 * 473 + 471 * 469 + 467 + 465 * 463 * 461 + 459 + 457 * 455 + 453 * 451 + 449 + 447 + 445 * 443 + 441 * 439 * 437 + 435 + 433 + 431 + 429 * 427 + 425 + 423 * 421 * 419 + 417 * 415 + 413 + 411 * 409 + 407 + 405 * 403 + 401 + ...