QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #862523 | #9980. Boolean Function Reconstruction | ucup-team1134# | WA | 14ms | 3712kb | C++23 | 10.5kb | 2025-01-19 02:29:13 | 2025-01-19 02:29: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;
map<string,string> MA;
string DFS(string S,int u){
if(u==3){
return MA[S];
}
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);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string solve3(int N,string S){
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++;
}
string bb;
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'){
bb+=char('a'+(inv[aa[i]-'a']));
}else{
bb+=aa[i];
}
}
chmin(re,mp(cn,bb));
}
return re.se;
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
for(int N=4;N<=4;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;
auto aa=solve3(N,S);
int cn=0;
for(int i=0;i<si(aa);i++){
if(a[i]=='|'||a[i]=='&') cn++;
}
//cout<<"if(S=="<<'"'<<S<<'"'<<") return "<<'"'<<aa<<'"'<<";\n";
MA[S]=aa;
//cout<<N<<" "<<cn<<" "<<S<<endl;
}
}
/*
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: 0
Wrong Answer
time: 14ms
memory: 3712kb
input:
7 2 0001 2 0111 2 1111 3 00010111 1 10 2 0101 5 00000000000000000000000000000001
output:
Yes (b&a) Yes (a|b) Yes T Yes ((c&(a|b))|(a&b)) No Yes a Yes ((b&)|)
result:
wrong answer invalid expressions 7 (test case 7)