QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#861418#9980. Boolean Function Reconstructionucup-team3802#WA 149ms4736kbC++202.3kb2025-01-18 17:23:262025-01-18 17:23:34

Judging History

This is the latest submission verdict.

  • [2025-01-18 17:23:34]
  • Judged
  • Verdict: WA
  • Time: 149ms
  • Memory: 4736kb
  • [2025-01-18 17:23:26]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define rep(i, l, r) for(ll i = l; i < r; i++)
#define all(ar) begin(ar), end(ar)

const ll a[5] = {
    0b00000000000000001111111111111111, 0b00000000111111110000000011111111,
    0b00001111000011110000111100001111, 0b00110011001100110011001100110011,
    0b01010101010101010101010101010101};

unordered_map<ll, string> st;
vector<vector<ll>> mask(14);

bool built = false;

void sol(int n, char top) {
    int sz = 1 << n;
    rep(i, 5 - n, 5) {
        mask[1].push_back(a[i]);
        st[a[i]] = top;
        top++;
    }
    st[0b11111111111111111111111111111111] = "T";
    st[0] = "F";
    rep(i, 2, 14) {
        rep(j, 1, i) {
            int k = i - j;
            if(j > k) break;
            for(ll x : mask[j])
                for(ll y : mask[k]) {
                    if(!st.count(x | y)) {
                        st[x | y] = "(" + st[x] + "|" + st[y] + ")";
                        mask[i].push_back(x | y);
                    }
                    if(!st.count(x & y)) {
                        st[x & y] = "(" + st[x] + "&" + st[y] + ")";
                        mask[i].push_back(x & y);
                    }
                }
        }
    }
    built = true;
}

bool f(int n, string s, char c, string &ans) {
    if(n >= 6) {
        int sz = s.size();
        int half = sz / 2;
        ans += "(";
        bool l = f(n - 1, s.substr(0, half), c + 1, ans);
        if(l) return true;
        ans += ")|(";
        ans += c;
        ans += "&(";
        bool r = f(n - 1, s.substr(half), c + 1, ans);
        if(r) return true;
        ans += "))";
        return false;
    } else {
        while(s.size() < 32u) s += s;
        ll x = stoll(s, nullptr, 2);
        if(!st.count(x)) return true;
        ans += st[x];
        return false;
    }
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    string ans;
    if(f(n, s, 'a', ans)) {
        cout << "No" << endl;
        return;
    }

    for(char &c : ans) {
        if(isdigit(c)) {
            c -= '0';
            c += 'a';
            c += n - 5;
        }
    }

    cout << "Yes" << endl;
    cout << ans << endl;
}

int main() {
    sol(5, '0');
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 149ms
memory: 4736kb

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

result:

wrong answer 1-th bit is incorrect (test case 6)