QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773152#7863. Parity GameCSQWA 3ms3724kbC++172.5kb2024-11-23 02:15:432024-11-23 02:15:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 02:15:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3724kb
  • [2024-11-23 02:15:43]
  • 提交

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+2<=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+2<=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()){ //first player losing 
			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: 2ms
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: 3636kb

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: 3640kb

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: 3648kb

input:

3 0
1 1 1
1 +
1

output:

Bob
1 +

result:

ok The player wins!

Test #5:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

3 1
1 0 1
1 *
1

output:

Bob
1 *

result:

ok The player wins!

Test #6:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

3 0
1 0 1
1 *
1

output:

Bob
1 +

result:

ok The player wins!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

2 1
0 1
1

output:

Alice
1 +

result:

ok The player wins!

Test #8:

score: 0
Accepted
time: 2ms
memory: 3608kb

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 +
2 *
2 +
2 *
2 +
2 *
2 *
2 +
2 *
2 +
2 +
2 *
2 +
2 +
2 *
2 +
2 *
2 *
2 +
2 +
2 +
2 +
2 *
2 +
2 +
2 *
2 +
2 +
2 *
2 +
2 +
2 +
2 *
2 +
2 +
2 +
2 +
2 *
2 +
2 +
2 +
2 *
2 +
2 +
2 *
2 +
2 *
2 +
2 *
2 +
2 *
2 +
2 +
2 *
2 *
2 *
2 *
2 +
2 +
2 +
2 +
2 +
2 *
2 *
2 +
2 *
2 +
2 +
2 +
2 *
2 *
2 ...

result:

ok The player wins!

Test #9:

score: 0
Accepted
time: 3ms
memory: 3636kb

input:

499 0
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 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 0 1 ...

output:

Bob
1 +
1 +
1 +
1 +
3 +
5 +
5 +
7 +
9 +
11 +
11 +
13 +
13 +
17 +
17 +
17 +
17 +
17 +
19 +
21 +
23 +
23 +
23 +
25 +
25 +
29 +
31 +
33 +
33 +
33 +
33 +
35 +
37 +
43 +
45 +
47 +
47 +
49 +
49 +
51 +
51 +
53 +
57 +
59 +
59 +
61 +
63 +
63 +
65 +
65 +
69 +
69 +
71 +
73 +
75 +
75 +
77 +
77 +
83 +
85 +
85 +
...

result:

ok The player wins!

Test #10:

score: -100
Wrong Answer
time: 2ms
memory: 3724kb

input:

500 0
0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 ...

output:

Alice
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 +
1 ...

result:

wrong answer format  Unexpected end of file - int32 expected