QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #772216 | #7863. Parity Game | Tom22l | TL | 1ms | 3800kb | C++17 | 4.4kb | 2024-11-22 17:35:43 | 2024-11-22 17:35:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
bool a[505];
int n,t;
bool check(int x,bool t){
int cnt1=0,cnt0=0,nwc=0;
for(int i=1;i<=n;i++){
if(i==x+1) continue;
if(i==x){
if(t==0){
cnt0++;
if(nwc%2==1)cnt1++;
nwc=0;
}else nwc++;
continue;
}
if(a[i]==0){
cnt0++;
if(nwc%2==1)cnt1++;
nwc=0;
}else nwc++;
}
if(nwc%2==1) cnt1++;
return (cnt1>=cnt0);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=Read(),t=Read();
for(int i=1;i<=n;i++){
a[i]=Read();
}
if(n%2==1) t^=1;
if(t==0){
if(n%2==1) {printf("Bob\n");fflush(stdout); }
else{
printf("Alice\n");
fflush(stdout);
n--;
printf("1 %c\n",(!(a[1]&&a[2])?'*':'+'));
fflush(stdout);a[1]=0;
for(int i=2;i<=n;i++) a[i]=a[i+1];
}
fflush(stdout);
while(n>1){
int x=Read();char ch=getchar();
while(ch!='+'&&ch!='*') ch=getchar();
if(ch=='+') a[x]^=a[x+1]; else a[x]&=a[x+1];
n--;
if(n==1) break;
for(int i=x+1;i<=n;i++) a[i]=a[i+1];
n--;
printf("1 %c\n",(!(a[1]&&a[2])?'*':'+'));
fflush(stdout);
a[1]=0;
for(int i=2;i<=n;i++) a[i]=a[i+1];
// for(int i=1;i<=n;i++) cout<<a[i]<<' ';
// cout<<endl;
}
}else{
if(n%2==1){ // bob is lp
bool flag=0;
for(int i=1;i<n;i++){
if(!check(i,a[i]^a[i+1])){
printf("Alice\n");fflush(stdout);
printf("%d +\n",i);fflush(stdout);flag=1;break;
}if(!check(i,a[i]&a[i+1])){
printf("Alice\n");fflush(stdout);
printf("%d *\n",i);fflush(stdout);flag=1;break;
}
}
if(flag){
n--;
while(n>1){
int x=Read();char ch=getchar();
if(!x) return 0;
while(ch!='+'&&ch!='*') ch=getchar();
if(ch=='+') a[x]^=a[x+1]; else a[x]&=a[x+1];
n--;
if(n==1) break;
for(int i=x+1;i<=n;i++) a[i]=a[i+1];
for(int i=1;i<n;i++){
if(!check(i,a[i]^a[i+1])){
printf("%d +\n",i);fflush(stdout);break;
}if(!check(i,a[i]&a[i+1])){
printf("%d *\n",i);fflush(stdout);break;
}
}
cout<<-1;
fflush(stdout);
n--;
}
}else{
printf("Bob\n");fflush(stdout);
while(n>1){
int x=Read();char ch=getchar();
while(ch!='+'&&ch!='*') ch=getchar();
if(ch=='+') a[x]^=a[x+1]; else a[x]&=a[x+1];
n--;
for(int i=x+1;i<=n;i++) a[i]=a[i+1];
bool ff=0;
for(int i=1;i<n;i++){
if(a[i]==0){
printf("%d +\n",i);fflush(stdout);
a[i]=a[i+1];
for(int j=i+1;j<n;j++) a[j]=a[j+1];
ff=1;
break;
}
}if(!ff){
if(a[n]==0) {printf("%d +\n",n-1);fflush(stdout);}
else{
printf("%d *\n",1);fflush(stdout);
}
}n--;
}
}
}else{ // alice is lp
if(!check(n+3,0)){
printf("Bob\n");fflush(stdout);
while(n>1){
int x=Read();char ch=getchar();
while(ch!='+'&&ch!='*') ch=getchar();
if(ch=='+') a[x]^=a[x+1]; else a[x]&=a[x+1];
n--;
if(n==1) break;
for(int i=x+1;i<=n;i++) a[i]=a[i+1];
for(int i=1;i<n;i++){
if(!check(i,a[i]^a[i+1])){
printf("%d +\n",i);fflush(stdout);break;
}if(!check(i,a[i]&a[i+1])){
printf("%d *\n",i);fflush(stdout);break;
}
}n--;
}
}else{
printf("Alice\n");fflush(stdout);
bool ff=0;
for(int i=1;i<n;i++){
if(a[i]==0){
printf("%d +\n",i);fflush(stdout);
a[i]=a[i+1];
for(int j=i+1;j<n;j++) a[j]=a[j+1];
ff=1;
break;
}
}if(!ff){
if(a[n]==0) {printf("%d +\n",n-1);fflush(stdout);}
else{
printf("%d *\n",1);fflush(stdout);
}
}n--;
while(n>1){
int x=Read();char ch=getchar();
while(ch!='+'&&ch!='*') ch=getchar();
if(ch=='+') a[x]^=a[x+1]; else a[x]&=a[x+1];
n--;
for(int i=x+1;i<=n;i++) a[i]=a[i+1];
ff=0;
for(int i=1;i<n;i++){
if(a[i]==0){
printf("%d +\n",i);fflush(stdout);
a[i]=a[i+1];
for(int j=i+1;j<n;j++) a[j]=a[j+1];
ff=1;
break;
}
}if(!ff){
if(a[n]==0) {printf("%d +\n",n-1);fflush(stdout);}
else{
printf("%d *\n",1);fflush(stdout);
}
}n--;
}
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
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: 3668kb
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: 3600kb
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: 3784kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 1 1 0 1 1 * 1
output:
Bob 1 *
result:
ok The player wins!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
3 0 1 0 1 1 * 1
output:
Bob 1 +
result:
ok The player wins!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3800kb
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 1 * -1