QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #470445 | #7863. Parity Game | ucup-team052# | WA | 2ms | 3892kb | C++23 | 4.0kb | 2024-07-10 13:48:18 | 2024-07-10 13:48:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 505
int a[N],b[N],n,t;
void op(int pos,int ty) // 0 +, 1 *
{
if(ty==0) a[pos]=a[pos]^a[pos+1];
else a[pos]=a[pos]*a[pos+1];
for(int i=pos+1;i<n;i++) a[i]=a[i+1];
n--;
}
void s00()
{
printf("Alice\n"); fflush(stdout);
while(n>=3)
{
printf("%d +\n",n-1); fflush(stdout);
op(n-1,0);
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
}
if(a[1]*a[2]==0) printf("1 *\n");
else printf("1 +\n");
}
void s11()
{
printf("Bob\n"); fflush(stdout);
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
while(n>=3)
{
printf("%d +\n",n-1); fflush(stdout);
op(n-1,0);
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
}
if(a[1]*a[2]==0) printf("1 *\n");
else printf("1 +\n");
}
int getop(int a,int b,int ned)
{
if(a*b==ned) return 1;
if((a^b)==ned) return 0;
assert(0);
}
int oddpos()
{
for(int i=1;i<=n;i+=2) if(a[i]==0) return 0;
return 1;
}
void s10()
{
int alice=0;
for(int i=1;i<=n;i+=2) if(a[i]==0) alice|=1;
if(alice)
{
printf("Alice\n"); fflush(stdout);
while(n>=3)
{
if(a[1]==0&&a[n]==0)
{
printf("1 *\n"); fflush(stdout);
op(1,1);
}
else if(a[1]==0)
{
int o=getop(a[n-1],a[n],0);
printf("%d %c\n",n-1,"+*"[o]); fflush(stdout);
op(n-1,o);
}
else
{
int o=getop(a[1],a[2],0);
printf("%d %c\n",1,"+*"[o]); fflush(stdout);
op(n-1,o);
}
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
}
}
else
{
printf("Bob\n"); fflush(stdout);
while(n>=2)
{
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
memcpy(b,a,sizeof(b));
for(int i=1;i<n;i++)
{
memcpy(a,b,sizeof(a));
op(i,0);
if(oddpos())
{
printf("%d +\n",i); fflush(stdout);
break;
}
memcpy(a,b,sizeof(a));
op(i,1);
if(oddpos())
{
printf("%d *\n",i); fflush(stdout);
break;
}
}
}
}
}
void s01()
{
int alice=0;
memcpy(b,a,sizeof(b));
int pos=0,o=0;
for(int i=1;i<n;i++)
{
memcpy(a,b,sizeof(a));
op(i,0);
if(oddpos())
{
alice=1,pos=i,o=0;
break;
}
memcpy(a,b,sizeof(a));
op(i,1);
if(oddpos())
{
alice=1,pos=i,o=1;
break;
}
}
if(alice)
{
printf("Alice\n"); fflush(stdout);
printf("%d %c\n",pos,"+*"[o]);
while(n>=2)
{
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
memcpy(b,a,sizeof(b));
for(int i=1;i<n;i++)
{
memcpy(a,b,sizeof(a));
op(i,0);
if(oddpos())
{
printf("%d +\n",i); fflush(stdout);
break;
}
memcpy(a,b,sizeof(a));
op(i,1);
if(oddpos())
{
printf("%d *\n",i); fflush(stdout);
break;
}
}
}
}
else
{
printf("Bob\n"); fflush(stdout);
while(n>=2)
{
int pos; char c; cin>>pos>>c;
if(c=='+') op(pos,0);
else op(pos,1);
if(a[1]==0&&a[n]==0)
{
printf("1 *\n"); fflush(stdout);
op(1,1);
}
else if(a[1]==0)
{
int o=getop(a[n-1],a[n],0);
printf("%d %c\n",n-1,"+*"[o]); fflush(stdout);
op(n-1,o);
}
else
{
int o=getop(a[1],a[2],0);
printf("%d %c\n",1,"+*"[o]); fflush(stdout);
op(n-1,o);
}
}
}
}
signed main()
{
cin>>n>>t;
for(int i=1;i<=n;i++) a[i]=read();
if(n%2==0&&t==0) s00();
else if(n%2==1&&t==1) s11();
else if(n%2==1&&t==0) s10();
else s01();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3892kb
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: 3888kb
input:
4 0 1 0 1 0 1 * 1
output:
Alice 3 + 1 *
result:
ok The player wins!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
5 1 1 1 1 0 0 4 + 1 * 1
output:
Bob 3 + 1 +
result:
ok The player wins!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 0 1 1 1 1 + 1
output:
Bob 1 +
result:
ok The player wins!
Test #5:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
3 1 1 0 1 1 * 1
output:
Bob 1 *
result:
ok The player wins!
Test #6:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
3 0 1 0 1 1 * 1
output:
Bob 1 +
result:
ok The player wins!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
2 1 0 1 1
output:
Alice 1 +
result:
ok The player wins!
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 3760kb
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 + 494 * 492 + 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 The interactor wins!