QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863700 | #9980. Boolean Function Reconstruction | pyiming | WA | 11ms | 3840kb | C++14 | 1.6kb | 2025-01-19 21:20:33 | 2025-01-19 21:20:39 |
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);
}
}
if(t.empty()){
cout<<"F";
}
else{
solve(0,t);
}
cout<<"\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
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: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 1 00 1 10 1 01 1 11
output:
Yes F No Yes a Yes T
result:
ok 4 lines, tightest: 0 out of 11 (4 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
16 2 0000 2 1000 2 0100 2 1100 2 0010 2 1010 2 0110 2 1110 2 0001 2 1001 2 0101 2 1101 2 0011 2 1011 2 0111 2 1111
output:
Yes F No No No No No No No Yes (a&b) No Yes (a&T) No Yes b No Yes (b|(a&T)) Yes T
result:
ok 16 lines, tightest: 2 out of 12 (16 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
256 3 00000000 3 10000000 3 01000000 3 11000000 3 00100000 3 10100000 3 01100000 3 11100000 3 00010000 3 10010000 3 01010000 3 11010000 3 00110000 3 10110000 3 01110000 3 11110000 3 00001000 3 10001000 3 01001000 3 11001000 3 00101000 3 10101000 3 01101000 3 11101000 3 00011000 3 10011000 3 01011000...
output:
Yes F No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 256 lines, tightest: 5 out of 14 (256 test cases)
Test #5:
score: 0
Accepted
time: 5ms
memory: 3584kb
input:
65536 4 0000000000000000 4 1000000000000000 4 0100000000000000 4 1100000000000000 4 0010000000000000 4 1010000000000000 4 0110000000000000 4 1110000000000000 4 0001000000000000 4 1001000000000000 4 0101000000000000 4 1101000000000000 4 0011000000000000 4 1011000000000000 4 0111000000000000 4 1111000...
output:
Yes F No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 65536 lines, tightest: 11 out of 18 (65536 test cases)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
168 4 0000000000000000 4 0000000000000001 4 0000000000000011 4 0000000000000101 4 0000000000000111 4 0000000000001111 4 0000000000010001 4 0000000000010011 4 0000000000010101 4 0000000000010111 4 0000000000011111 4 0000000000110011 4 0000000000110111 4 0000000000111111 4 0000000001010101 4 000000000...
output:
Yes F Yes (a&(b&(c&d))) Yes (b&(c&d)) Yes (a&(c&d)) Yes ((b&(c&d))|(a&(c&d))) Yes (c&d) Yes (a&(b&d)) Yes ((b&(c&d))|(a&(b&d))) Yes (a&((c&d)|(b&d))) Yes ((b&(c&d))|(a&((c&d)|(b&d)))) Yes ((c&d)|(a&(b&d))) Yes (b&d) Yes ((b&d)|(a&(c&d))) Yes ((c&d)|(b&d)) Yes (a&d) Yes ((b&(c&d))|(a&d)) Yes ((c&d)|(...
result:
ok 168 lines, tightest: 11 out of 18 (168 test cases)
Test #7:
score: 0
Accepted
time: 11ms
memory: 3712kb
input:
7581 5 00000000000000000000000000000000 5 00000000000000000000000000000001 5 00000000000000000000000000000011 5 00000000000000000000000000000101 5 00000000000000000000000000000111 5 00000000000000000000000000001111 5 00000000000000000000000000010001 5 00000000000000000000000000010011 5 0000000000000...
output:
Yes F Yes (a&(b&(c&(d&e)))) Yes (b&(c&(d&e))) Yes (a&(c&(d&e))) Yes ((b&(c&(d&e)))|(a&(c&(d&e)))) Yes (c&(d&e)) Yes (a&(b&(d&e))) Yes ((b&(c&(d&e)))|(a&(b&(d&e)))) Yes (a&((c&(d&e))|(b&(d&e)))) Yes ((b&(c&(d&e)))|(a&((c&(d&e))|(b&(d&e))))) Yes ((c&(d&e))|(a&(b&(d&e)))) Yes (b&(d&e)) Yes ((b&(d&e))|(...
result:
ok 7581 lines, tightest: 22 out of 26 (7581 test cases)
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 3840kb
input:
14 1 01 2 0111 3 00010111 4 0001011101111111 5 00000001000101110001011101111111 6 0000000100010111000101110111111100010111011111110111111111111111 7 00000000000000010000000100010111000000010001011100010111011111110000000100010111000101110111111100010111011111110111111111111111 8 00000000000000010000...
output:
Yes a Yes (b|(a&T)) Yes ((b&c)|(a&(c|(b&T)))) Yes (((c&d)|(b&(d|(c&T))))|(a&((d|(c&T))|(b&T)))) Yes (((c&(d&e))|(b&((d&e)|(c&(e|(d&T))))))|(a&(((d&e)|(c&(e|(d&T))))|(b&((e|(d&T))|(c&T)))))) Yes ((((d&(e&f))|(c&((e&f)|(d&(f|(e&T))))))|(b&(((e&f)|(d&(f|(e&T))))|(c&((f|(e&T))|(d&T))))))|(a&((((e&f)|(d&...
result:
wrong answer 43 operations, you can't use more than 42 operations (test case 6)