QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879703 | #9980. Boolean Function Reconstruction | as_lyr | WA | 0ms | 3968kb | C++14 | 1.0kb | 2025-02-02 11:05:37 | 2025-02-02 11:05:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=16;
int n;
char s[1<<N];
bool o[1<<N];
int f[1<<N];
struct str{
int op;
string s;
};
str dfs(int x,int sum){
if(x==n){
if(f[sum])
return {1,"T"};
else
return {0,"F"};
}
str res,it;
res.op=-1;
it=dfs(x+1,sum|(1<<x));
if(it.op==0)
res={0,"F"};
else if(it.op==1)
res.s+=x+'a';
else{
res.s+='(';
res.s+=x+'a';
res.s+='&';
res.s+=it.s;
res.s+=')';
}
it=dfs(x+1,sum);
if(it.op==1)
res={1,"T"};
else if(it.op==0)
;
else{
res.s+='|';
res.s+=it.s;
}
return res;
}
void solve(){
scanf("%d",&n);
scanf("%s",s);
for(int i=0;i<(1<<n);i++)
o[i]=s[i]-'0';
for(int i=0;i<(1<<n);i++)
f[i]=o[i];
for(int p=0;p<n;p++)
for(int i=0;i<(1<<n);i++)
if(i&(1<<p))
f[i]+=f[i^(1<<p)];
for(int i=0;i<(1<<n);i++)
if(f[i]&&o[i]==0){
puts("No");
return ;
}
puts("Yes");
str it=dfs(0,0);
cout<<it.s<<'\n';
}
int main(){
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3968kb
input:
7 2 0001 2 0111 2 1111 3 00010111 1 10 2 0101 5 00000000000000000000000000000001
output:
Yes (a&b) Yes a|b Yes T Yes (a&b|c)|(b&c) No Yes a Yes (a&(b&(c&(d&e))))
result:
wrong answer invalid expressions 9 (test case 2)