QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#862485 | #9980. Boolean Function Reconstruction | ucup-team139# | WA | 1ms | 5860kb | C++14 | 1.1kb | 2025-01-19 01:54:59 | 2025-01-19 01:55:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n;
bool fa[17][1<<16];
bool fo[17][1<<16];
string fatina(int bs, int i) {
string alpha = "";
alpha+=('a'+i);
//cerr<<i<<' '<<bs<<' '<<fa[i+1][bs]<<' '<<fo[i+1][bs]<<endl;
if(fa[i+1][bs]==1) return "T";
if(fo[i+1][bs]==0) return "F";
string l = fatina(bs<<1, i-1); // x=0
string r = fatina(1|(bs<<1), i-1); //x=1
if(l=="F" && r=="T") return alpha;
if(l==r) return l;
if(l=="F") return alpha+"&("+r+")";
if(r=="T") return "("+l+")|"+alpha;
return "("+l+")|("+alpha+"&("+r+"))";
}
void solve() {
string sf;
cin>>n>>sf;
for(int i=0; i<(1<<n); ++i) fa[0][i]=fo[0][i]=(sf[i]=='1');
for(int i=0; i<(1<<n); ++i) if(fa[0][i]) for(int j=0; j<n; ++j) {
if(!fa[0][i|(1<<j)]) {
cout<<"No\n";
return;
}
}
for(int j=1; j<=n; ++j) {
for(int i=0; 2*i+1<(1<<n); ++i) {
fa[j][i] = fa[j-1][2*i]&fa[j-1][2*i+1];
fo[j][i] = fo[j-1][2*i]|fo[j-1][2*i+1];
}
}
cout<<"Yes\n"<<fatina(0,n-1)<<'\n';
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int t;
cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5860kb
input:
7 2 0001 2 0111 2 1111 3 00010111 1 10 2 0101 5 00000000000000000000000000000001
output:
Yes b&(a) Yes (a)|b Yes T Yes (b&(a))|(c&((a)|b)) No Yes a Yes e&(d&(c&(b&(a))))
result:
wrong answer invalid expressions 9 (test case 1)