QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#879703#9980. Boolean Function Reconstructionas_lyrWA 0ms3968kbC++141.0kb2025-02-02 11:05:372025-02-02 11:05:39

Judging History

This is the latest submission verdict.

  • [2025-02-02 11:05:39]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3968kb
  • [2025-02-02 11:05:37]
  • 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+=it.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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
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:

wrong answer invalid expressions 9 (test case 2)