QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #862491 | #9980. Boolean Function Reconstruction | ucup-team1134# | WA | 20ms | 3712kb | C++23 | 7.0kb | 2025-01-19 01:57:04 | 2025-01-19 01:57:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
string AND(vi pos){
if(si(pos)==0) return "T";
else if(si(pos)==1) return string(1,char('a'+pos[0]));
else{
vi A,B;
for(int i=0;i<si(pos);i++){
if(i<si(pos)/2) A.pb(pos[i]);
else B.pb(pos[i]);
}
auto aa=AND(A),bb=AND(B);
string res;
res+='(';
res+=aa;
res+='&';
res+=bb;
res+=')';
return res;
}
}
string OR(vst pos){
if(si(pos)==0) return "F";
else if(si(pos)==1) return pos[0];
else{
vst A,B;
for(int i=0;i<si(pos);i++){
if(i<si(pos)/2) A.pb(pos[i]);
else B.pb(pos[i]);
}
auto aa=OR(A),bb=OR(B);
string res;
res+='(';
res+=aa;
res+='|';
res+=bb;
res+=')';
return res;
}
}
string solve(int N,string S){
vst ans;
string U(1<<N,'0');
vi iru(1<<N);
for(int bit=0;bit<(1<<N);bit++){
bool ok=true;
int rem=(1<<N)-1-bit;
for(int T=rem;;T=(T-1)&rem){
ok&=(S[bit|T]=='1');
if(T==0) break;
}
if(ok){
iru[bit]=true;
for(int T=rem;;T=(T-1)&rem){
U[bit|T]='1';
if(T==0) break;
}
}
}
if(U==S){
for(int bit=(1<<N)-1;bit>=0;bit--){
if(iru[bit]){
bool kesu=true;
for(int i=0;i<N;i++){
if(bit&(1<<i)){
kesu&=(iru[bit^(1<<i)]);
}
}
//if(kesu) iru[bit]=false;
}
}
for(int bit=0;bit<(1<<N);bit++){
if(iru[bit]){
vi fff;
for(int i=0;i<N;i++){
if(bit&(1<<i)) fff.pb(i);
}
ans.pb(AND(fff));
}
}
for(int i=0;i<N;i++){
for(int bit=0;bit<(1<<N);bit++){
if(!(bit&(1<<i))){
chmax(U[bit|(1<<i)],U[bit]);
}
}
}
assert(U==S);
return OR(ans);
}else{
U=S;
for(int i=0;i<N;i++){
for(int bit=0;bit<(1<<N);bit++){
if(!(bit&(1<<i))){
chmax(U[bit|(1<<i)],U[bit]);
}
}
}
assert(U!=S);
return "NG";
}
}
string X;
string DFS(string S,int u){
if(u==1){
if(S=="0000") return "F";
if(S=="0001") return "(b&a)";
if(S=="0011") return "b";
if(S=="0101") return "a";
if(S=="0111") return "(b|a)";
if(S=="1111") return "T";
return "";
}
if(u==0){
if(S=="00") return "F";
else if(S=="11") return "T";
else if(S=="01") return "a";
else{
//cout<<X<<endl;
exit(1);
return "oh";
}
}else{
string A,B;
for(int bit=0;bit<si(S)/2;bit++){
if(S[bit]=='0'){
if(S[bit+si(S)/2]=='0'){
A+='0';
B+='0';
}else{
A+='1';
B+='0';
}
}else{
if(S[bit+si(S)/2]=='0'){
//cout<<X<<endl;
exit(1);
}else{
A+='1';
B+='1';
}
}
}
if(A==B){
auto aa=DFS(A,u-1);
return aa;
}
auto aa=DFS(A,u-1),bb=DFS(B,u-1);
if(aa=="F"){
return bb;
}
if(aa=="T"){
string Z;
Z+='(';
Z+=char('a'+u);
Z+='|';
Z+=bb;
Z+=')';
return Z;
}
if(bb=="F"){
string Z;
Z+='(';
Z+=char('a'+u);
Z+='&';
Z+=aa;
Z+=')';
return Z;
}
if(bb=="T"){
return "T";
}
string Z;
Z+='(';
Z+='(';
Z+=char('a'+u);
Z+='&';
Z+=aa;
Z+=')';
Z+='|';
Z+=bb;
Z+=')';
return Z;
}
}
string solve2(int N,string S){
X=S;
string U=S;
for(int i=0;i<N;i++){
for(int bit=0;bit<(1<<N);bit++){
if(!(bit&(1<<i))){
chmax(U[bit|(1<<i)],U[bit]);
}
}
}
if(U!=S) return "NG";
return DFS(S,N-1);
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
/*
for(int N=1;N<=5;N++){
for(ll bit=0;bit<(1LL<<(1LL<<N));bit++){
string S;
for(int i=0;i<(1LL<<N);i++){
if(bit&(1LL<<((1LL<<N)-1-i))) S+='1';
else S+='0';
}
auto a=solve2(N,S);
if(a=="NG") continue;
int cn=0;
for(int i=0;i<si(a);i++){
if(a[i]=='|'||a[i]=='&') cn++;
}
cout<<N<<" "<<cn<<" "<<S<<" "<<a<<endl;
}
}
*/
/*
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while(1){
int N=7;
string S(1<<N,'0');
for(int bi=0;bi<(1<<N);bi++){
int z=rand()%20;
if(z==0){
for(int y=0;y<(1<<N);y++){
if((y&bi)==bi) S[y]='1';
}
}
}
auto a=solve2(N,S);
if(a=="NG") continue;
int cn=0;
for(int i=0;i<si(a);i++){
if(a[i]=='|'||a[i]=='&') cn++;
}
cout<<N<<" "<<cn<<" "<<(1<<(N-1))+10<<endl;
}
*/
int Q;cin>>Q;
while(Q--){
int N;cin>>N;
string S;cin>>S;
auto ans=solve(N,S);
if(ans=="NG") cout<<"No\n";
else{
cout<<"Yes\n";
cout<<ans<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
7 2 0001 2 0111 2 1111 3 00010111 1 10 2 0101 5 00000000000000000000000000000001
output:
Yes (a&b) Yes (a|(b|(a&b))) Yes ((T|a)|(b|(a&b))) Yes (((a&b)|(a&c))|((b&c)|(a&(b&c)))) No Yes (a|(a&b)) Yes ((a&b)&(c&(d&e)))
result:
ok 7 lines, tightest: 8 out of 14 (7 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 1 00 1 10 1 01 1 11
output:
Yes F No Yes a Yes (T|a)
result:
ok 4 lines, tightest: 1 out of 11 (4 test cases)
Test #3:
score: 0
Accepted
time: 1ms
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|(a&b)) No Yes (b|(a&b)) No Yes (a|(b|(a&b))) Yes ((T|a)|(b|(a&b)))
result:
ok 16 lines, tightest: 4 out of 12 (16 test cases)
Test #4:
score: 0
Accepted
time: 1ms
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: 12 out of 14 (256 test cases)
Test #5:
score: -100
Wrong Answer
time: 20ms
memory: 3712kb
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:
wrong answer 19 operations, you can't use more than 18 operations (test case 43691)