QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#879704	#9980. Boolean Function Reconstruction	as_lyr	WA	13ms	3968kb	C++14	1.1kb	2025-02-02 11:07:02	2025-02-02 11:07:02

Judging History

This is the latest submission verdict.

[2025-02-02 11:07:02]
Judged

Verdict: WA
Time: 13ms
Memory: 3968kb

Show

[2025-02-02 11:07:02]
Submitted

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;
		res.s+='|';
		res.s+=it.s;
		res.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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

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:

ok 7 lines, tightest: 4 out of 14 (7 test cases)

Test #2:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

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: 3840kb

input:

output:

Yes
F
No
No
No
No
No
No
No
Yes
(a&b)
No
Yes
a
No
Yes
((a&b)|b)
No
Yes
(a|b)
Yes
T

result:

ok 16 lines, tightest: 2 out of 12 (16 test cases)

Test #4:

score: 0

Accepted

time: 0ms

memory: 3840kb

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: 6 out of 14 (256 test cases)

Test #5:

score: 0

Accepted

time: 13ms

memory: 3840kb

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: 14 out of 18 (65536 test cases)

Test #6:

score: 0

Accepted

time: 0ms

memory: 3968kb

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
((a&(b&(c&d)))|(b&(c&d)))
Yes
(a&((b&(c&d))|(c&d)))
Yes
((a&((b&(c&d))|(c&d)))|(b&(c&d)))
Yes
((a&((b&(c&d))|(c&d)))|((b&(c&d))|(c&d)))
Yes
(a&(b&((c&d)|d)))
Yes
((a&(b&((c&d)|d)))|(b&(c&d)))
Yes
(a&((b&((c&d)|d))|(c&d)))
Yes
((a&((b&((c&d)|d))|(c&d)))|(b&(c&d)))
Yes
((a&...

result:

ok 168 lines, tightest: 14 out of 18 (168 test cases)

Test #7:

score: -100

Wrong Answer

time: 10ms

memory: 3968kb

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
((a&(b&(c&(d&e))))|(b&(c&(d&e))))
Yes
(a&((b&(c&(d&e)))|(c&(d&e))))
Yes
((a&((b&(c&(d&e)))|(c&(d&e))))|(b&(c&(d&e))))
Yes
((a&((b&(c&(d&e)))|(c&(d&e))))|((b&(c&(d&e)))|(c&(d&e))))
Yes
(a&(b&((c&(d&e))|(d&e))))
Yes
((a&(b&((c&(d&e))|(d&e))))|(b&(c&(d&e))))
Yes
(a&((b&(...

result:

wrong answer 27 operations, you can't use more than 26 operations (test case 134)