QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #869729 | #9980. Boolean Function Reconstruction | Andyqian7 | WA | 40ms | 3584kb | C++26 | 2.4kb | 2025-01-25 13:09:18 | 2025-01-25 13:09:25 |
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 vector<string> &expr, char split)
{
if (expr.empty())
{
if (split == '&')
{
return "T";
}
else
{
return "F";
}
}
string ret;
for (int i = 1; i < expr.size(); i++)
{
ret += '(';
}
ret += expr[0];
for (int i = 1; i < expr.size(); i++)
{
ret += split;
ret += expr[i];
ret += ')';
}
return ret;
}
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 k = 0; k <= n; k++)
for (int i = 0; i < 1 << n; i++)
{
if (__builtin_popcount(i) != k)
continue;
if (s[i] == '1')
{
vis[i] = 1;
if (i)
for (int j = (i - 1) & i;; j = (j - 1) & i)
{
if (vis[j])
{
vis[i] = 0;
}
if (!j)
break;
}
}
}
vector<string> v;
for (int i = 0; i < 1 << n; i++)
{
if (vis[i])
{
vector<string> tmp;
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
{
string cur;
cur += j + 97;
tmp.push_back(cur);
}
}
v.push_back(merge(tmp, '&'));
}
}
cout << merge(v, '|') << endl;
}
}
詳細信息
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&c))|(b&c)) No Yes a Yes ((((a&b)&c)&d)&e)
result:
ok 7 lines, tightest: 5 out of 14 (7 test cases)
Test #2:
score: 0
Accepted
time: 1ms
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 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: 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: 5 out of 14 (256 test cases)
Test #5:
score: 0
Accepted
time: 40ms
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: 11 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&c)&d) Yes (((a&c)&d)|((b&c)&d)) Yes (c&d) Yes ((a&b)&d) Yes (((a&b)&d)|((b&c)&d)) Yes (((a&b)&d)|((a&c)&d)) Yes ((((a&b)&d)|((a&c)&d))|((b&c)&d)) Yes (((a&b)&d)|(c&d)) Yes (b&d) Yes ((b&d)|((a&c)&d)) Yes ((b&d)|(c&d)) Yes (a&d) Yes ((a&d)|((b&c)&d)) Yes ...
result:
ok 168 lines, tightest: 11 out of 18 (168 test cases)
Test #7:
score: -100
Wrong Answer
time: 18ms
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&c)&d)&e) Yes ((((a&c)&d)&e)|(((b&c)&d)&e)) Yes ((c&d)&e) Yes (((a&b)&d)&e) Yes ((((a&b)&d)&e)|(((b&c)&d)&e)) Yes ((((a&b)&d)&e)|(((a&c)&d)&e)) Yes (((((a&b)&d)&e)|(((a&c)&d)&e))|(((b&c)&d)&e)) Yes ((((a&b)&d)&e)|((c&d)&e)) Yes ((b&d)&e) Yes (((b...
result:
wrong answer 29 operations, you can't use more than 26 operations (test case 3081)