QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #288985 | #7863. Parity Game | ucup-team1134# | WA | 0ms | 3516kb | C++23 | 8.0kb | 2023-12-23 14:37:53 | 2023-12-23 14:37:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
map<string,bool> MA[2];
char win='1';
bool solve(string S,bool te){
if(si(S)==1){
if(S[0]==win){
if(te==0) return true;
else return false;
}else{
if(te==0) return false;
else return true;
}
}
for(int i=0;i+1<si(S);i++){
int a=(S[i]-'0')^(S[i+1]-'0');
string T;
T+=S.substr(0,i);
T+=char('0'+a);
T+=S.substr(i+2);
if(!solve(T,te^1)) return MA[te][S]=true;
}
for(int i=0;i+1<si(S);i++){
int a=(S[i]-'0')*(S[i+1]-'0');
string T;
T+=S.substr(0,i);
T+=char('0'+a);
T+=S.substr(i+2);
if(!solve(T,te^1)) return MA[te][S]=true;
}
return MA[te][S]=false;
}
int main(){
int N,type;cin>>N>>type;
vector<int> A(N);
for(int i=0;i<N;i++) cin>>A[i];
auto op=[&](vector<int> &S,int id,char c,bool output){
if(output) cout<<id+1<<" "<<c<<endl;
if(c=='+'){
S[id]=(S[id]^S[id+1]);
S.erase(S.begin()+(id+1));
}else{
S[id]=(S[id]*S[id+1]);
S.erase(S.begin()+(id+1));
}
};
auto losecheck0=[&](vector<int> S){
for(int i=0;i<si(S);i+=2){
if(S[i]==0) return false;
}
return true;
};
auto wincheck1=[&](vector<int> S){
int x=0;
for(int i=0;i<si(S)/2;i++){
if(S[2*i]=='1') x++;
else break;
}
for(int i=si(S)/2-1;i>=0;i--){
if(S[2*i+1]=='1') x++;
else break;
}
if(x>=si(S)/2) return true;
else return false;
};
if(type==0){
if(N%2==0){
cout<<"Alice"<<endl;
while(si(A)>2){
op(A,0,'+',1);
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
}
if(A[0]&&A[1]) op(A,0,'+',1);
else op(A,0,'*',1);
return 0;
}else{
if(losecheck0(A)){
cout<<"Bob"<<endl;
while(si(A)>1){
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
for(int i=0;i+1<si(A);i++){
vector<int> U=A;
op(U,i,'+',0);
if(losecheck0(U)){
op(A,i,'+',1);
break;
}
U=A;
op(U,i,'*',0);
if(losecheck0(U)){
op(A,i,'*',1);
break;
}
}
}
}else{
cout<<"Alice"<<endl;
while(si(A)>1){
for(int i=0;i<si(A);i+=2){
if(A[i]==0){
if(i){
if(A[i-2]==A[i-1]){
op(A,i-2,'+',1);
break;
}else{
op(A,i-2,'*',1);
break;
}
}else{
if(A[i+1]==A[i+2]){
op(A,i+1,'+',1);
break;
}else{
op(A,i+1,'*',1);
break;
}
}
}
}
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
}
}
}
}else{
if(N%2==1){
cout<<"Bob"<<endl;
while(si(A)>1){
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
if(si(A)==2){
if(A[0]&&A[1]) op(A,0,'+',1);
else op(A,0,'*',1);
}else{
op(A,0,'+',1);
}
}
return 0;
}else{
if(wincheck1(A)){
cout<<"Alice"<<endl;
while(si(A)>2){
for(int i=0;;i+=2){
if(i==si(A)){
if(A[i-1]){
op(A,i-2,'*',1);
}else{
op(A,i-2,'+',1);
}
break;
}
if(A[i]==0){
if(i==0){
if(A[i+1]){
op(A,i,'+',1);
}else{
assert(false);
}
}else{
if(A[i-1]){
op(A,i-2,'*',1);
}else{
op(A,i-2,'+',1);
}
}
break;
}
}
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
}
if(A[0]==A[1]) op(A,0,'*',1);
else op(A,0,'+',1);
return 0;
}else{
cout<<"Bob"<<endl;
while(si(A)>1){
int a;char b;cin>>a>>b;
op(A,a-1,b,0);
if(si(A)==1) break;
for(int i=0;i+1<si(A);i++){
vector<int> U=A;
op(U,i,'+',0);
if(!wincheck1(U)){
op(A,i,'+',1);
break;
}
U=A;
op(U,i,'*',0);
if(!wincheck1(U)){
op(A,i,'*',1);
break;
}
}
}
}
}
}
/*
for(int N=2;N<=12;N++){
int cn=0;
for(int bit=0;bit<(1<<N);bit++){
string S;
for(int i=0;i<N;i++){
if(bit&(1<<i)) S+='1';
else S+='0';
}
if(N&1) continue;
int x=0;
for(int i=0;i<N/2;i++){
if(S[2*i]=='1') x++;
else break;
}
for(int i=N/2-1;i>=0;i--){
if(S[2*i+1]=='1') x++;
else break;
}
assert(solve(S,0)==(x>=N/2));
if(solve(S,0)&&S[0]=='1'&&S.back()=='1'){
cn++;
cout<<S<<" "<<solve(S,0)<<endl;
}
}
//cout<<cn<<" ";
}
*/
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3516kb
input:
4 1 0 1 0 1 1 + 1 * 0
output:
Bob 1 +
result:
wrong answer The interactor wins!