QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863700#9980. Boolean Function ReconstructionpyimingWA 11ms3840kbC++141.6kb2025-01-19 21:20:332025-01-19 21:20:39

Judging History

你现在查看的是最新测评结果

  • [2025-01-19 21:20:39]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:3840kb
  • [2025-01-19 21:20:33]
  • 提交

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)