QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #870042 | #9980. Boolean Function Reconstruction | Andyqian7 | WA | 41ms | 3584kb | C++26 | 1.6kb | 2025-01-25 14:32:48 | 2025-01-25 14:33:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, vis[1 << 15];
string s;
bool check()
{
for (int i = 0; i < 1 << n; i++)
{
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
continue;
int nxt = 1 << j | i;
if (s[i] > s[nxt])
return 0;
}
}
return 1;
}
string merge(const string &a, const string &b, char op)
{
if (a == "F")
return op == '&' ? "F" : b;
if (a == "T")
return op == '&' ? b : "T";
if (b == "F")
return op == '&' ? "F" : a;
if (b == "T")
return op == '&' ? a : "T";
return '(' + a + op + b + ')';
}
string sol(int l, int r, int m)
{
bool sign = 0;
int mi = 1, ma = 0;
for (int i = l; i <= r; i++)
mi = min(mi, vis[i]), ma = max(ma, vis[i]);
if (mi == 1)
return "T";
if (ma == 0)
return "F";
int mid = l + r >> 1;
string cur;
cur += n - m + 96;
return merge(sol(l, mid, m + 1), merge(sol(mid + 1, r, m + 1), cur, '&'), '|');
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> s;
for (int i = 0; i < 1 << n; i++)
{
vis[i] = 0;
}
if (!check())
{
cout << "No" << endl;
continue;
}
cout << "Yes" << endl;
for (int i = 0; i < 1 << n; i++)
{
if (s[i] == '1')
{
vis[i] = 1;
}
}
cout << sol(0, (1 << n) - 1, 0) << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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)|((a|b)&c)) No Yes (a|(a&b)) Yes ((((a&b)&c)&d)&e)
result:
ok 7 lines, tightest: 4 out of 14 (7 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
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 (a&b) No Yes (a|(a&b)) No Yes b No Yes (a|b) Yes T
result:
ok 16 lines, tightest: 2 out of 12 (16 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
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: 6 out of 14 (256 test cases)
Test #5:
score: 0
Accepted
time: 41ms
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: 14 out of 18 (65536 test cases)
Test #6:
score: 0
Accepted
time: 1ms
memory: 3584kb
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 (((a&b)&c)&d) Yes ((b&c)&d) Yes (((a|(a&b))&c)&d) Yes (((a|b)&c)&d) Yes (c&d) Yes (((a&b)|((a&b)&c))&d) Yes (((a&b)|(b&c))&d) Yes (((a&b)|((a|(a&b))&c))&d) Yes (((a&b)|((a|b)&c))&d) Yes (((a&b)|c)&d) Yes ((b|(b&c))&d) Yes ((b|((a|b)&c))&d) Yes ((b|c)&d) Yes (((a|(a&b))|((a|(a&b))&c))&d) Ye...
result:
ok 168 lines, tightest: 14 out of 18 (168 test cases)
Test #7:
score: -100
Wrong Answer
time: 15ms
memory: 3584kb
input:
7581 5 00000000000000000000000000000000 5 00000000000000000000000000000001 5 00000000000000000000000000000011 5 00000000000000000000000000000101 5 00000000000000000000000000000111 5 00000000000000000000000000001111 5 00000000000000000000000000010001 5 00000000000000000000000000010011 5 0000000000000...
output:
Yes F Yes ((((a&b)&c)&d)&e) Yes (((b&c)&d)&e) Yes ((((a|(a&b))&c)&d)&e) Yes ((((a|b)&c)&d)&e) Yes ((c&d)&e) Yes ((((a&b)|((a&b)&c))&d)&e) Yes ((((a&b)|(b&c))&d)&e) Yes ((((a&b)|((a|(a&b))&c))&d)&e) Yes ((((a&b)|((a|b)&c))&d)&e) Yes ((((a&b)|c)&d)&e) Yes (((b|(b&c))&d)&e) Yes (((b|((a|b)&c))&d)&e) Ye...
result:
wrong answer 27 operations, you can't use more than 26 operations (test case 4947)