QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773150 | #7863. Parity Game | CSQ | WA | 1ms | 3720kb | C++17 | 2.5kb | 2024-11-23 02:08:22 | 2024-11-23 02:08:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a ; i <(b) ; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fi first
#define se second
typedef __int128 ll ;
typedef pair<int, int> pii;
typedef vector<int> vi;
int a[1000],b[1000],n,t;
bool debug = 0;
void add(int i,int print){
if(print)cout<<i<<" +"<<endl;
a[i] = (a[i]+a[i+1])%2;
for(int j=i+1;j<n;j++)a[j] = a[j+1];
n--;
if(debug){
for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<'\n';
}
}
void mult(int i,int print){
if(print)cout<<i<<" *"<<endl;
a[i] = a[i]*a[i+1];
for(int j=i+1;j<n;j++)a[j] = a[j+1];
n--;
if(debug){
for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<'\n';
}
}
void read_move(){
int x;
char c;
cin>>x>>c;
if(c == '+')add(x,0);
else mult(x,0);
}
bool check(){ //return 1 iif all zeros are on even squares
for(int i=1;i<=n;i+=2){
if(!a[i])return 0;
}
return 1;
}
void sett(){for(int i=1;i<=n;i++)b[i] = a[i];}
void reset(int m){for(int i=1;i<=m;i++)a[i] = b[i];n=m;}
pii get(){
if(n&1)return {-1,-1};
sett();
int m = n;
pii mov = {-1,-1};
for(int i=1;i+1<=m;i++){
reset(m);
add(i,0);
if(check()){
mov = {i,0};
break;
}
reset(m);
mult(i,0);
if(check()){
mov = {i,1};
break;
}
}
reset(m);
return mov;
}
void Alice(){
pii mov = get();
//cout<<mov.fi<<" "<<mov.se<<'\n';
if(mov.se == 0)add(mov.fi,1);
if(mov.se == 1)mult(mov.fi,1);
if(n>1){
read_move();
Alice();
}
}
void Bob(){
if(n <= 1)return;
for(int i=1;i<=n;i+=2){
if(a[i] == 0){
if(i-2>=1){
if(!a[i-1] || !a[i-2])mult(i-2,1);
else add(i-2,1);
}else{
if(!a[i+1] || !a[i+2])mult(i+1,1);
else add(i+1,1);
}
read_move();
Bob();
return;
}
}
}
int main()
{
cin>>n>>t;
for(int i=1;i<=n;i++)cin>>a[i];
if(n%2 == 0 && !t){
cout<<"Alice"<<'\n';
for(int i=1;i+1<=n;i+=2){
add(1,1);
read_move();
}
if(!a[1] || !a[2])mult(1,1);
else add(1,1);
}else if(n%2 == 1 && t){
cout<<"Bob"<<'\n';
read_move();
for(int i=1;i+1<=n;i+=2){
add(1,1);
read_move();
}
if(!a[1] || !a[2])mult(1,1);
else add(1,1);
}else if(n%2 == 0){
pii mov = get();
if(mov.fi != -1){
cout<<"Alice"<<'\n';
Alice();
}else{
cout<<"Bob"<<'\n';
read_move();
Bob();
}
}else{
if(check()){
cout<<"Bob"<<'\n';
read_move();
Alice();
}else{
cout<<"Alice"<<'\n';
Bob();
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
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: 3624kb
input:
4 0 1 0 1 0 1 * 1
output:
Alice 1 + 1 *
result:
ok The player wins!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3720kb
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: 3632kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3632kb
input:
3 1 1 0 1 1 * 0
output:
Bob 1 +
result:
wrong answer The interactor wins!