QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#861418 | #9980. Boolean Function Reconstruction | ucup-team3802# | WA | 149ms | 4736kb | C++20 | 2.3kb | 2025-01-18 17:23:26 | 2025-01-18 17:23:34 |
Judging History
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)