QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300700#7863. Parity Gamewillow#TL 1ms3868kbC++142.8kb2024-01-08 17:21:012024-01-08 17:21:01

Judging History

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

  • [2024-01-08 17:21:01]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3868kb
  • [2024-01-08 17:21:01]
  • 提交

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((j - i) % 2 == 1 && a[i] == 1) {
			++ cnt[1];
		}
		else {
			cnt[a[i]] += j - i;
		}
		i = j;
	}
	int flg = -1;
	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);
			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;
			}
			assert(pos != -1);
			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: 3800kb

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

output:


result: