QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #862513 | #9980. Boolean Function Reconstruction | ucup-team1134# | TL | 1948ms | 15692kb | C++23 | 9.4kb | 2025-01-19 02:17:14 | 2025-01-19 02:17:14 |
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==2){
if(S=="00010011") return "(b&(a|c))";
if(S=="00010101") return "(a&(b|c))";
if(S=="00110111") return "(b|(a&c))";
if(S=="01010111") return "(a|(b&c))";
}
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"){
if(bb=="T"){
return "T";
}
if(bb=="F"){
return string(1,char('a'+u));
}
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());
/*
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ma=0;
while(1){
int N=8;
string S(1<<N,'0');
for(int bi=0;bi<(1<<N);bi++){
int z=rand()%10;
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;
pair<int,string> re=mp(INF,"");
for(int q=0;q<20;q++){
vi id(N);iota(all(id),0);
shuffle(all(id),rng);
string nex(1<<N,'0');
for(int i=0;i<(1<<N);i++){
if(S[i]=='1'){
int to=0;
for(int j=0;j<N;j++){
if(i&(1<<j)) to|=(1<<id[j]);
}
nex[to]='1';
}
}
auto aa=solve2(N,nex);
int cn=0;
for(int i=0;i<si(aa);i++){
if(aa[i]=='|'||aa[i]=='&') cn++;
}
chmin(re,mp(cn,nex));
}
int cn=0;
for(int i=0;i<si(a);i++){
if(a[i]=='|'||a[i]=='&') cn++;
}
cn=re.fi;
if(chmax(ma,cn)) cout<<ma<<" "<<(1<<(N-1))+10<<" "<<a<<" "<<S<<endl;
//cout<<N<<" "<<ma<<" "<<(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";
while(1){
vi id(N);iota(all(id),0);
shuffle(all(id),rng);
string nex(1<<N,'0');
for(int i=0;i<(1<<N);i++){
if(S[i]=='1'){
int to=0;
for(int j=0;j<N;j++){
if(i&(1<<j)) to|=(1<<id[j]);
}
nex[to]='1';
}
}
auto aa=solve2(N,nex);
int cn=0;
for(int i=0;i<si(aa);i++){
if(aa[i]=='|'||aa[i]=='&') cn++;
}
if(cn<=((1<<(N-1))+10)){
vi inv(N);
for(int i=0;i<N;i++){
inv[id[i]]=i;
}
for(int i=0;i<si(aa);i++){
if('a'<=aa[i]&&aa[i]<='z'){
cout<<char('a'+(inv[aa[i]-'a']));
}else{
cout<<aa[i];
}
}
cout<<"\n";
break;
}
}
}
}
}
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 (b|a) Yes T Yes ((b&(a|c))|(a&c)) No Yes a Yes (c&(a&(e&(b&d))))
result:
ok 7 lines, tightest: 4 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
result:
ok 4 lines, tightest: 0 out of 11 (4 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
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 (b&a) No Yes a No Yes b No Yes (a|b) Yes T
result:
ok 16 lines, tightest: 1 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: 4 out of 14 (256 test cases)
Test #5:
score: 0
Accepted
time: 21ms
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: 8 out of 18 (65536 test cases)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
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 (b&(a&(c&d))) Yes (b&(d&c)) Yes (c&(a&d)) Yes ((b&(c&d))|(c&(a&d))) Yes (c&d) Yes (b&(a&d)) Yes (b&(d&(c|a))) Yes ((c&(a&d))|(b&(a&d))) Yes ((c&(d&(a|b)))|(b&(d&a))) Yes ((b&(d&(a|c)))|(c&d)) Yes (d&b) Yes ((b&d)|(c&(a&d))) Yes (d&(b|c)) Yes (d&a) Yes (d&(a|(c&b))) Yes (d&(c|a)) Yes ((b&d)...
result:
ok 168 lines, tightest: 8 out of 18 (168 test cases)
Test #7:
score: 0
Accepted
time: 79ms
memory: 3840kb
input:
7581 5 00000000000000000000000000000000 5 00000000000000000000000000000001 5 00000000000000000000000000000011 5 00000000000000000000000000000101 5 00000000000000000000000000000111 5 00000000000000000000000000001111 5 00000000000000000000000000010001 5 00000000000000000000000000010011 5 0000000000000...
output:
Yes F Yes (d&(c&(a&(e&b)))) Yes (d&(b&(e&c))) Yes (c&(d&(a&e))) Yes (e&((a&(d&c))|(d&(b&c)))) Yes (d&(e&c)) Yes (e&(b&(d&a))) Yes (b&(d&(e&(c|a)))) Yes ((b&(e&(a&d)))|(c&(e&(a&d)))) Yes ((a&((b&(d&e))|(d&(e&c))))|(b&(d&(e&c)))) Yes ((c&(d&e))|(a&(d&(b&e)))) Yes (e&(b&d)) Yes ((c&(e&(d&(b|a))))|(e&(b...
result:
ok 7581 lines, tightest: 18 out of 26 (7581 test cases)
Test #8:
score: 0
Accepted
time: 50ms
memory: 8992kb
input:
14 1 01 2 0111 3 00010111 4 0001011101111111 5 00000001000101110001011101111111 6 0000000100010111000101110111111100010111011111110111111111111111 7 00000000000000010000000100010111000000010001011100010111011111110000000100010111000101110111111100010111011111110111111111111111 8 00000000000000010000...
output:
Yes a Yes (b|a) Yes ((a&(c|b))|(c&b)) Yes ((d&(b|(a|c)))|((b&(a|c))|(a&c))) Yes ((c&((e&(b|(a|d)))|((b&(a|d))|(a&d))))|((e&((b&(a|d))|(a&d)))|(b&(a&d)))) Yes ((a&((e&(d|(f|(b|c))))|((d&(f|(b|c)))|((f&(b|c))|(b&c)))))|((e&((d&(f|(b|c)))|((f&(b|c))|(b&c))))|((d&((f&(b|c))|(b&c)))|(f&(b&c))))) Yes ((f&...
result:
ok 14 lines, tightest: 68 out of 74 (14 test cases)
Test #9:
score: 0
Accepted
time: 39ms
memory: 7248kb
input:
14 1 01 2 0001 3 00010111 4 0000000100010111 5 00000001000101110001011101111111 6 0000000000000001000000010001011100000001000101110001011101111111 7 00000000000000010000000100010111000000010001011100010111011111110000000100010111000101110111111100010111011111110111111111111111 8 00000000000000000000...
output:
Yes a Yes (a&b) Yes ((c&(b|a))|(b&a)) Yes ((b&((d&(c|a))|(c&a)))|(d&(c&a))) Yes ((c&((e&(a|(d|b)))|((a&(d|b))|(d&b))))|((e&((a&(d|b))|(d&b)))|(a&(d&b)))) Yes ((e&((c&((d&(b|(f|a)))|((b&(f|a))|(f&a))))|((d&((b&(f|a))|(f&a)))|(b&(f&a)))))|((c&((d&((b&(f|a))|(f&a)))|(b&(f&a))))|(d&(b&(f&a))))) Yes ((d&...
result:
ok 14 lines, tightest: 68 out of 74 (14 test cases)
Test #10:
score: 0
Accepted
time: 34ms
memory: 7168kb
input:
14 1 00 2 0001 3 00000001 4 0000000100010111 5 00000000000000010000000100010111 6 0000000000000001000000010001011100000001000101110001011101111111 7 00000000000000000000000000000001000000000000000100000001000101110000000000000001000000010001011100000001000101110001011101111111 8 00000000000000000000...
output:
Yes F Yes (b&a) Yes (c&(a&b)) Yes ((c&((b&(d|a))|(d&a)))|(b&(d&a))) Yes ((a&((e&((d&(c|b))|(c&b)))|(d&(c&b))))|(e&(d&(c&b)))) Yes ((c&((e&((f&(a|(d|b)))|((a&(d|b))|(d&b))))|((f&((a&(d|b))|(d&b)))|(a&(d&b)))))|((e&((f&((a&(d|b))|(d&b)))|(a&(d&b))))|(f&(a&(d&b))))) Yes ((a&((b&((g&((c&(f|(d|e)))|((f&(...
result:
ok 14 lines, tightest: 33 out of 42 (14 test cases)
Test #11:
score: 0
Accepted
time: 26ms
memory: 5632kb
input:
14 1 00 2 0000 3 00000001 4 0000000000000001 5 00000000000000010000000100010111 6 0000000000000000000000000000000100000000000000010000000100010111 7 00000000000000000000000000000001000000000000000100000001000101110000000000000001000000010001011100000001000101110001011101111111 8 00000000000000000000...
output:
Yes F Yes F Yes (b&(a&c)) Yes (c&(d&(b&a))) Yes ((a&((b&((c&(e|d))|(e&d)))|(c&(e&d))))|(b&(c&(e&d)))) Yes ((c&((b&((f&((a&(d|e))|(d&e)))|(a&(d&e))))|(f&(a&(d&e)))))|(b&(f&(a&(d&e))))) Yes ((f&((e&((b&((c&(d|(a|g)))|((d&(a|g))|(a&g))))|((c&((d&(a|g))|(a&g)))|(d&(a&g)))))|((b&((c&((d&(a|g))|(a&g)))|(d...
result:
ok 14 lines, tightest: 0 out of 11 (14 test cases)
Test #12:
score: 0
Accepted
time: 56ms
memory: 11892kb
input:
1 15 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...
output:
Yes ((b&((d&((g&((k&((e&((m&((a&(f|(l|(o|(h|(i|(c|(n|j))))))))|((f&(l|(o|(h|(i|(c|(n|j)))))))|((l&(o|(h|(i|(c|(n|j))))))|((o&(h|(i|(c|(n|j)))))|((h&(i|(c|(n|j))))|((i&(c|(n|j)))|((c&(n|j))|(n&j)))))))))|((a&((f&(l|(o|(h|(i|(c|(n|j)))))))|((l&(o|(h|(i|(c|(n|j))))))|((o&(h|(i|(c|(n|j)))))|((h&(i|(c|(n...
result:
ok 1 lines, tightest: 12868 out of 16394 (1 test case)
Test #13:
score: 0
Accepted
time: 74ms
memory: 15692kb
input:
1 15 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000100000000000000010000000100010111000000000000000000000000000000000000000...
output:
Yes ((k&((b&((m&((h&((n&((f&(d|(i|(g|(j|(c|(o|(l|(a|e)))))))))|((d&(i|(g|(j|(c|(o|(l|(a|e))))))))|((i&(g|(j|(c|(o|(l|(a|e)))))))|((g&(j|(c|(o|(l|(a|e))))))|((j&(c|(o|(l|(a|e)))))|((c&(o|(l|(a|e))))|((o&(l|(a|e)))|((l&(a|e))|(a&e))))))))))|((f&((d&(i|(g|(j|(c|(o|(l|(a|e))))))))|((i&(g|(j|(c|(o|(l|(a|...
result:
ok 1 lines, tightest: 11438 out of 16394 (1 test case)
Test #14:
score: 0
Accepted
time: 43ms
memory: 9564kb
input:
1 15 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
Yes ((n&((c&((b&((e&((o&((f&((g&((i&(d|(j|(l|(k|(a|(h|m)))))))|((d&(j|(l|(k|(a|(h|m))))))|((j&(l|(k|(a|(h|m)))))|((l&(k|(a|(h|m))))|((k&(a|(h|m)))|((a&(h|m))|(h&m))))))))|((i&((d&(j|(l|(k|(a|(h|m))))))|((j&(l|(k|(a|(h|m)))))|((l&(k|(a|(h|m))))|((k&(a|(h|m)))|((a&(h|m))|(h&m)))))))|((d&((j&(l|(k|(a|(...
result:
ok 1 lines, tightest: 11438 out of 16394 (1 test case)
Test #15:
score: 0
Accepted
time: 31ms
memory: 6784kb
input:
1 15 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
Yes ((l&((a&((m&((d&((i&((b&((h&((o&((g&(c|(n|(e|(j|(k|f))))))|((c&(n|(e|(j|(k|f)))))|((n&(e|(j|(k|f))))|((e&(j|(k|f)))|((j&(k|f))|(k&f)))))))|((g&((c&(n|(e|(j|(k|f)))))|((n&(e|(j|(k|f))))|((e&(j|(k|f)))|((j&(k|f))|(k&f))))))|((c&((n&(e|(j|(k|f))))|((e&(j|(k|f)))|((j&(k|f))|(k&f)))))|((n&((e&(j|(k|f...
result:
ok 1 lines, tightest: 8006 out of 16394 (1 test case)
Test #16:
score: 0
Accepted
time: 1948ms
memory: 3840kb
input:
65536 6 0000001101111111000111111111111101111111111111111111111111111111 6 0000000000000000000100110011011100000000000000000001001100111111 6 0101010101110111011101111111111101110111111111111111111111111111 6 0000001100000011000000110001011100011111001111110011111100111111 6 000000010001011100000001...
output:
Yes ((a&((e&(b|(f|(c|d))))|((b&(f|(c|d)))|(f|d))))|((e&(f|(c|d)))|((b&(f|(c|d)))|((f&(c|d))|(c&d))))) Yes ((b&(e&(a|(c|d))))|(e&((a&(c&d))|(c&(f&d))))) Yes ((f&(a|(e|(d|b))))|(a|((e&(d|b))|(d&b)))) Yes ((d&((c&(f|(b|(e&a))))|((f&b)|(a&(e&b)))))|((c&(f|b))|(f&(b&(e|a))))) Yes ((c&((a&(d|(b|f)))|(b&(f...
result:
ok 65536 lines, tightest: 38 out of 42 (65536 test cases)
Test #17:
score: -100
Time Limit Exceeded
input:
65536 7 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 7 00000001000100010001000101110111000100010111011101110111011111110001000101110111011101110111111100010001011101110111011111111111 7 000000010001001100000001001101...
output:
Yes (c&(g&(d&(a&(e&(b&f)))))) Yes ((b&((d&(f|(e|(a|g))))|((f&(e|a))|((e&(a|g))|(a&(g|c))))))|((d&((f&((e&(a|(g|c)))|a))|((e&(a|(g&c)))|(a&g))))|((f&(e&a))|(e&(a&g))))) Yes ((d&((g&((c&((e&(b|(f|a)))|(b|f)))|((e&(b|f))|((b&(f|a))|(f&a)))))|((c&((e&(b|(f|a)))|(b|f)))|((e&(b|(f&a)))|((b&(f|a))|(f&a))))...