QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#863695 | #9980. Boolean Function Reconstruction | pyiming | WA | 0ms | 3712kb | C++14 | 1.5kb | 2025-01-19 21:18:50 | 2025-01-19 21:18:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
bool check(){
for(int i=0;i<(1<<n);i++) if(s[i]=='0'){
for(int j=i;j;j=(j-1)&i) if(s[((j-1)&i)]=='1'){
return false;
}
}
return true;
}
void solve(int now,vector<int> &t){
vector<int> t0,t1;
for(int i:t){
if(i&(1<<now)){
t1.push_back(i);
}
else{
t0.push_back(i);
}
}
t.clear();
if(now+1==n){
if(t0.size()){
cout<<"T";
}
else{
cout<<char('a'+now);
}
return;
}
if(t0.size()&&t1.size()){
cout<<"(";
solve(now+1,t0);
cout<<"|("<<char('a'+now)<<"&";
solve(now+1,t1);
cout<<"))";
}
else if(t0.size()){
solve(now+1,t0);
}
else{
cout<<"("<<char('a'+now)<<"&";
solve(now+1,t1);
cout<<")";
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--){
cin>>n>>s;
if(!check()){
cout<<"No\n";
continue;
}
cout<<"Yes\n";
vector<int> t;
for(int i=0;i<(1<<n);i++) if(s[i]=='1'){
bool flag=1;
for(int j=i;j;j=(j-1)&i) if(s[((j-1)&i)]=='1'){
flag=0;
break;
}
if(flag){
t.push_back(i);
}
}
solve(0,t);
cout<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
7 2 0001 2 0111 2 1111 3 00010111 1 10 2 0101 5 00000000000000000000000000000001
output:
Yes (a&b) Yes (b|(a&T)) Yes T Yes ((b&c)|(a&(c|(b&T)))) No Yes (a&T) Yes (a&(b&(c&(d&e))))
result:
ok 7 lines, tightest: 5 out of 14 (7 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
4 1 00 1 10 1 01 1 11
output:
Yes a No Yes a Yes T
result:
wrong answer 1-th bit is incorrect (test case 1)