QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#861998#9980. Boolean Function Reconstructionucup-team4435#AC ✓375ms4224kbC++203.5kb2025-01-18 21:02:292025-01-18 21:02:43

Judging History

你现在查看的是最新测评结果

  • [2025-01-18 21:02:43]
  • 评测
  • 测评结果:AC
  • 用时:375ms
  • 内存:4224kb
  • [2025-01-18 21:02:29]
  • 提交

answer

#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"


#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
//#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}

const int INFi = 2e9;
const ll INF = 2e18;

int a[1 << 15];
int b[1 << 15];
vi p;

string solve(int up, int n) {
    int cnt = 0;
    rep(mask, 1 << n) cnt += a[up | mask];
    if (n == 1) {
        if (cnt == 2) {
            return "T";
        }
        if (cnt == 0) {
            return "F";
        }
        assert(cnt == 1 && a[up | 1]);
        string res;
        res += char('a' + p[0]);
        return res;
    }
    auto L = solve(up, n - 1);
    auto R = solve(up | (1 << (n - 1)), n - 1);
    if (L == R) {
        return L;
    }
    assert(L != "T" && R != "F");
    if (R == "T") {
        R.clear();
    } else {
        R += '&';
    }
    R += char('a' + p[n - 1]);
    if (R.size() > 1) R = "(" + R + ")";
    // L | R
    if (L == "F") {
        return R;
    }
    return "(" + L + "|" + R + ")";
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n; cin >> n;
    rep(mask, 1 << n) {
        char x; cin >> x;
        b[mask] = x - '0';
    }
    rep(mask, 1 << n) {
        rep(bit, n) {
            if (mask & (1 << bit)) {
                if (b[mask^(1<<bit)] > b[mask]) {
                    cout << "No\n";
                    return;
                }
            }
        }
    }
    cout << "Yes\n";
    p.resize(n);
    iota(all(p), 0);
    while (true) {
        shuffle(all(p), rng);
        rep(mask, 1 << n) {
            int mask2 = 0;
            rep(bit, n) if (mask & (1 << bit)) mask2 |= (1 << p[bit]);
            a[mask] = b[mask2];
        }
        auto result = solve(0, n);
        int cnt = count(all(result), '&') + count(all(result), '|');
        if (cnt > (1 << (n - 1)) + 10) {
            continue;
        }
        cout << result << '\n';
        return;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;

    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

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

result:

ok 7 lines, tightest: 4 out of 14 (7 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

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: 3712kb

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: 3712kb

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: 4 out of 14 (256 test cases)

Test #5:

score: 0
Accepted
time: 14ms
memory: 3712kb

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: 9 out of 18 (65536 test cases)

Test #6:

score: 0
Accepted
time: 1ms
memory: 3712kb

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

result:

ok 168 lines, tightest: 9 out of 18 (168 test cases)

Test #7:

score: 0
Accepted
time: 9ms
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&e)&d)&b)&c)
Yes
(((d&e)&c)&b)
Yes
(((d&e)&c)&a)
Yes
((((c&b)|(c&a))&d)&e)
Yes
((c&e)&d)
Yes
(((d&e)&b)&a)
Yes
((((d&b)&e)&a)|(((d&b)&e)&c))
Yes
((((e&c)&a)&d)|(((e&a)&d)&b))
Yes
((((d&a)&c)&e)|((((d&a)|(d&c))&e)&b))
Yes
(((d&c)&e)|((((d&c)&e)|((d&e)&a))&b))
Yes
((d&e)&b)
Yes
(((b|((a...

result:

ok 7581 lines, tightest: 20 out of 26 (7581 test cases)

Test #8:

score: 0
Accepted
time: 3ms
memory: 3968kb

input:

14
1
01
2
0111
3
00010111
4
0001011101111111
5
00000001000101110001011101111111
6
0000000100010111000101110111111100010111011111110111111111111111
7
00000000000000010000000100010111000000010001011100010111011111110000000100010111000101110111111100010111011111110111111111111111
8
00000000000000010000...

output:

Yes
a
Yes
(b|a)
Yes
((c&b)|((c|b)&a))
Yes
(((d&c)|((d|c)&a))|(((d|c)|a)&b))
Yes
((((a&c)&b)|(((a&c)|((a|c)&b))&e))|((((a&c)|((a|c)&b))|(((a|c)|b)&e))&d))
Yes
(((((a&d)&c)|(((a&d)|((a|d)&c))&f))|((((a&d)|((a|d)&c))|(((a|d)|c)&f))&b))|(((((a&d)|((a|d)&c))|(((a|d)|c)&f))|((((a|d)|c)|f)&b))&e))
Yes
((((...

result:

ok 14 lines, tightest: 68 out of 74 (14 test cases)

Test #9:

score: 0
Accepted
time: 4ms
memory: 3968kb

input:

14
1
01
2
0001
3
00010111
4
0000000100010111
5
00000001000101110001011101111111
6
0000000000000001000000010001011100000001000101110001011101111111
7
00000000000000010000000100010111000000010001011100010111011111110000000100010111000101110111111100010111011111110111111111111111
8
00000000000000000000...

output:

Yes
a
Yes
(b&a)
Yes
((b&c)|((b|c)&a))
Yes
(((d&c)&b)|(((d&c)|((d|c)&b))&a))
Yes
((((d&b)&c)|(((d&b)|((d|b)&c))&e))|((((d&b)|((d|b)&c))|(((d|b)|c)&e))&a))
Yes
(((((d&f)&b)&c)|((((d&f)&b)|(((d&f)|((d|f)&b))&c))&e))|(((((d&f)&b)|(((d&f)|((d|f)&b))&c))|((((d&f)|((d|f)&b))|(((d|f)|b)&c))&e))&a))
Yes
((((...

result:

ok 14 lines, tightest: 68 out of 74 (14 test cases)

Test #10:

score: 0
Accepted
time: 4ms
memory: 3840kb

input:

14
1
00
2
0001
3
00000001
4
0000000100010111
5
00000000000000010000000100010111
6
0000000000000001000000010001011100000001000101110001011101111111
7
00000000000000000000000000000001000000000000000100000001000101110000000000000001000000010001011100000001000101110001011101111111
8
00000000000000000000...

output:

Yes
F
Yes
(a&b)
Yes
((a&b)&c)
Yes
(((b&c)&d)|(((b&c)|((b|c)&d))&a))
Yes
((((c&e)&a)&b)|((((c&e)&a)|(((c&e)|((c|e)&a))&b))&d))
Yes
(((((c&b)&a)&e)|((((c&b)&a)|(((c&b)|((c|b)&a))&e))&f))|(((((c&b)&a)|(((c&b)|((c|b)&a))&e))|((((c&b)|((c|b)&a))|(((c|b)|a)&e))&f))&d))
Yes
((((((d&a)&c)&g)&f)|(((((d&a)&c)...

result:

ok 14 lines, tightest: 33 out of 42 (14 test cases)

Test #11:

score: 0
Accepted
time: 4ms
memory: 3968kb

input:

14
1
00
2
0000
3
00000001
4
0000000000000001
5
00000000000000010000000100010111
6
0000000000000000000000000000000100000000000000010000000100010111
7
00000000000000000000000000000001000000000000000100000001000101110000000000000001000000010001011100000001000101110001011101111111
8
00000000000000000000...

output:

Yes
F
Yes
F
Yes
((b&a)&c)
Yes
(((a&c)&d)&b)
Yes
((((a&c)&e)&b)|((((a&c)&e)|(((a&c)|((a|c)&e))&b))&d))
Yes
(((((f&a)&b)&c)&e)|(((((f&a)&b)&c)|((((f&a)&b)|(((f&a)|((f|a)&b))&c))&e))&d))
Yes
((((((d&g)&c)&a)&f)|(((((d&g)&c)&a)|((((d&g)&c)|(((d&g)|((d|g)&c))&a))&f))&b))|((((((d&g)&c)&a)|((((d&g)&c)|(((d...

result:

ok 14 lines, tightest: 0 out of 11 (14 test cases)

Test #12:

score: 0
Accepted
time: 5ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...

output:

Yes
((((((((((((((d&i)&b)&j)&l)&n)&a)&o)|((((((((d&i)&b)&j)&l)&n)&a)|(((((((d&i)&b)&j)&l)&n)|((((((d&i)&b)&j)&l)|(((((d&i)&b)&j)|((((d&i)&b)|(((d&i)|((d|i)&b))&j))&l))&n))&a))&o))&e))|(((((((((d&i)&b)&j)&l)&n)&a)|(((((((d&i)&b)&j)&l)&n)|((((((d&i)&b)&j)&l)|(((((d&i)&b)&j)|((((d&i)&b)|(((d&i)|((d|i)&...

result:

ok 1 lines, tightest: 12868 out of 16394 (1 test case)

Test #13:

score: 0
Accepted
time: 5ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000100000000000000010000000100010111000000000000000000000000000000000000000...

output:

Yes
((((((((((((((i&d)&k)&f)&o)&h)&n)|(((((((i&d)&k)&f)&o)&h)|((((((i&d)&k)&f)&o)|(((((i&d)&k)&f)|((((i&d)&k)|(((i&d)|((i|d)&k))&f))&o))&h))&n))&g))|((((((((i&d)&k)&f)&o)&h)|((((((i&d)&k)&f)&o)|(((((i&d)&k)&f)|((((i&d)&k)|(((i&d)|((i|d)&k))&f))&o))&h))&n))|(((((((i&d)&k)&f)&o)|(((((i&d)&k)&f)|((((i&...

result:

ok 1 lines, tightest: 11438 out of 16394 (1 test case)

Test #14:

score: 0
Accepted
time: 3ms
memory: 4224kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((c&i)&o)&n)&b)&d)&j)&k)&m)|(((((((((c&i)&o)&n)&b)&d)&j)&k)|((((((((c&i)&o)&n)&b)&d)&j)|(((((((c&i)&o)&n)&b)&d)|((((((c&i)&o)&n)&b)|(((((c&i)&o)&n)|((((c&i)&o)|(((c&i)|((c|i)&o))&n))&b))&d))&j))&k))&m))&f))|((((((((((c&i)&o)&n)&b)&d)&j)&k)|((((((((c&i)&o)&n)&b)&d)&j)|(((((((c&i)&o)&n...

result:

ok 1 lines, tightest: 11438 out of 16394 (1 test case)

Test #15:

score: 0
Accepted
time: 4ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((g&h)&n)&i)&m)&f)&k)&c)&o)&l)|((((((((((g&h)&n)&i)&m)&f)&k)&c)&o)|(((((((((g&h)&n)&i)&m)&f)&k)&c)|((((((((g&h)&n)&i)&m)&f)&k)|(((((((g&h)&n)&i)&m)&f)|((((((g&h)&n)&i)&m)|(((((g&h)&n)&i)|((((g&h)&n)|(((g&h)|((g|h)&n))&i))&m))&f))&k))&c))&o))&l))&j))|(((((((((((g&h)&n)&i)&m)&f)&k)&c)&...

result:

ok 1 lines, tightest: 8006 out of 16394 (1 test case)

Test #16:

score: 0
Accepted
time: 164ms
memory: 3712kb

input:

65536
6
0000001101111111000111111111111101111111111111111111111111111111
6
0000000000000000000100110011011100000000000000000001001100111111
6
0101010101110111011101111111111101110111111111111111111111111111
6
0000001100000011000000110001011100011111001111110011111100111111
6
000000010001011100000001...

output:

Yes
(((((e|a)&d)|(((e|a)|d)&f))|((((e&a)|d)|f)&b))|((((e|d)|f)|b)&c))
Yes
((((e&b)&c)|(((e&b)|(((f&e)|(e&b))&c))&d))|(((e&b)|(((e&b)|(e&c))&d))&a))
Yes
((((d&f)|((d|f)&e))|(((d|f)|e)&b))|a)
Yes
(((f&c)|(((f&c)|(((f&c)|(c&e))&a))&d))|((((c|((f|c)&e))|((f|c)&a))|(((f|c)|(((f|c)|e)&a))&d))&b))
Yes
((((...

result:

ok 65536 lines, tightest: 41 out of 42 (65536 test cases)

Test #17:

score: 0
Accepted
time: 330ms
memory: 3584kb

input:

65536
7
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
7
00000001000100010001000101110111000100010111011101110111011111110001000101110111011101110111111100010001011101110111011111111111
7
000000010001001100000001001101...

output:

Yes
((((((c&g)&a)&e)&d)&b)&f)
Yes
(((((d&f)&a)|(((d&f)|(((d|c)|f)&a))&b))|(((d&a)|((d|a)&b))&g))|((((((d&c)&f)|((d|f)&a))|(((d|f)|a)&b))|(((((d&c)|(d&f))|a)|b)&g))&e))
Yes
(((((a|((a|e)&g))&c)&b)|((((a&e)&c)|(((a|e)|c)&b))&d))|(((((a&e)&c)|(((a|e)|c)&b))|((((a|((a|e)&g))|c)|b)&d))&f))
Yes
(((((f&a)&...

result:

ok 65536 lines, tightest: 74 out of 74 (65536 test cases)

Test #18:

score: 0
Accepted
time: 186ms
memory: 3712kb

input:

16384
8
0000000000000000000000000000000000000000000000000000000000010001000000000000000000000000000100010000000000010001000100010011011100000000000000000000000000010001000000000001000100010001011101110000000000000001000100010011011100010001000101110011011101111111
8
000101010101011100010101011101110...

output:

Yes
(((((((e&a)&h)&c)&g)&f)|((((((e&a)&h)&c)&g)|((((e&a)&h)|((((e&a)&h)|(((e&a)|((e|a)&h))&c))&g))&f))&d))|((((((e&a)&h)&g)|((((e&a)&h)|(((e&a)|((e|a)&h))&g))&f))|(((((e&a)&h)|((((e&a)|(e&h))|(((e&a)|((e|a)&h))&c))&g))|((((e&a)|((e|a)&h))|(((e|a)|(((e|a)|h)&c))&g))&f))&d))&b))
Yes
(((((d&f)|((d|f)&h...

result:

ok 16384 lines, tightest: 138 out of 138 (16384 test cases)

Test #19:

score: 0
Accepted
time: 178ms
memory: 3840kb

input:

4096
9
00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000101110000000000000000000000010001011100000...

output:

Yes
(((((((b&f)|(((h|b)&f)&g))&e)&i)|((((f|((b|f)&g))&e)&i)&a))|(((((f|((b|f)&g))&e)&i)|((((((h&b)&f)&g)&e)|((((b&f)&g)|(((b|f)|g)&e))&i))&a))&c))|((((((f|((b|f)&g))&e)&i)|((((((h&b)&f)&g)&e)|((((b&f)&g)|(((b|f)|g)&e))&i))&a))|((((((b&f)&g)&e)|((((b&f)&g)|((((h|b)|f)|g)&e))&i))|(((((b&f)|(f&g))&e)|(...

result:

ok 4096 lines, tightest: 265 out of 266 (4096 test cases)

Test #20:

score: 0
Accepted
time: 105ms
memory: 3840kb

input:

1024
10
0000000000000000000000000000000100000000000000110000000000000011000000000000000100000000000000110000000000000011000000010000001100000000000000110000000000000011000000000000001100000011000001110000000000000011000000000000001100000011000001110000001100011111000000000000001100000000000000110000...

output:

Yes
(((((((f&i)&c)&j)|((((((f|i)&c)&j)|((((f&i)&c)|(((f&i)|c)&j))&e))|(((((f&i)&c)|(c&j))|((((f&i)&c)|(((f&i)|c)&j))&e))&a))&b))|((((((f&i)&c)&j)|(((f&c)&j)&e))|(((((f&i)&c)|(((f&i)|c)&j))|(((((f&i)&c)|(((f&i)|c)&j))|(((f&c)|(((f&i)|c)&j))&e))&a))&b))&g))|((((((((f&i)&c)&j)|(((f&c)&j)&e))|((((f&c)&j...

result:

ok 1024 lines, tightest: 504 out of 522 (1024 test cases)

Test #21:

score: 0
Accepted
time: 59ms
memory: 3840kb

input:

256
11
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((b&e)&h)&d)|((b&h)&c))&j)&i)|((((((((b&h)&d)|(((b&h)|(((b|e)&h)&d))&c))&j)&i)|(((((((b&e)&h)|((b&h)&d))|(((b&h)|(((b|e)&h)&d))&c))&j)&i)&a))|(((((((b&h)&d)|(((b&h)|(((b|e)&h)&d))&c))&j)&i)|(((((((b&e)&h)&d)&c)&j)|((((((b&e)&h)|((b&h)&d))|(((b&h)|(((b|e)&h)&d))&c))&j)&i))&a))&g))&k))|(((((...

result:

ok 256 lines, tightest: 884 out of 1034 (256 test cases)

Test #22:

score: 0
Accepted
time: 30ms
memory: 3968kb

input:

64
12
000101011111111101111111111111110001011111111111011111111111111100010111111111110111111111111111000101111111111101111111111111110001010111111111011111111111111100010111111111110111111111111111000101111111111101111111111111110001011111111111111111111111111101111111111111111111111111111111011111...

output:

Yes
(((((((d|((((d|j)|b)|f)&k))|((d|(((((d|j)|b)|h)|f)&k))&g))|(((d|b)|k)&a))|((((((d|j)|b)|k)|(((((d|j)|b)|((((d|j)|b)|h)&f))|k)&g))|a)&e))|((((d|k)|((((((d|j)|b)|f)|k)|((((((d|j)|b)|h)|f)|k)&g))&a))|e)&l))|((((((((d|b)|(((d|b)|(((d|j)|b)&h))&f))|k)|((((d|b)|(((d|j)|b)&f))|k)&g))|a)|e)|l)&i))|(((((...

result:

ok 64 lines, tightest: 1928 out of 2058 (64 test cases)

Test #23:

score: 0
Accepted
time: 18ms
memory: 3840kb

input:

16
13
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000011111111111111111111111111111100000000000000000000000000000000000000...

output:

Yes
((((((((((((k&e)&f)&m)&b)&d)&c)&g)|((((((((k&e)&f)&m)&b)|(((((k&e)&f)|((e&f)&m))&b)&d))&c)&g)&l))|(((((((((k&e)&f)&m)&b)&d)&c)&g)|((((((((k&e)&f)&m)&b)|(((((k&e)&f)&m)|((((k&e)&f)|((e&f)&m))&b))&d))&c)&g)&l))&a))|((((((((((k&e)&f)&m)&b)&d)|((((((k&e)&f)&m)&b)|(((((k&e)&f)&m)|((((k&e)&f)|((e&f)&m...

result:

ok 16 lines, tightest: 3333 out of 4106 (16 test cases)

Test #24:

score: 0
Accepted
time: 8ms
memory: 3968kb

input:

4
14
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
(((((((((((e&k)&a)&b)|((((e&k)&a)|(((e&k)|((e|k)&a))&b))&m))&l)&f)|((((((e&k)&b)&m)&l)|(((((e&k)&b)&m)|((((e&k)|((e|k)&b))|(((e|k)|b)&m))&l))&f))&i))|((((((((e&k)&b)|((((e&k)&a)|(((e&k)|((e|k)&a))&b))&m))&l)&f)|((((((e&k)&b)&m)&l)|(((((e&k)&b)&m)|((((e&k)|((e|k)&b))|(((e|k)|b)&m))&l))&f))&i))|((...

result:

ok 4 lines, tightest: 3193 out of 8202 (4 test cases)

Test #25:

score: 0
Accepted
time: 8ms
memory: 3840kb

input:

4
14
0000000000000000000000000000000000000000000000000001000100010101000000000000000101010101010101010001010101010101011101110111111100000000000000000000000000000001000000000000000000010101010101010000000100010001010101010101011101010101010101010111111111111111000000000000000000010101010101010000000...

output:

Yes
((((((((((((n&e)&j)&g)|(((((n&e)&c)|((n&e)&j))&g)&l))|((((((n&e)&c)|((n&e)&j))&g)|((((n&e)|(((n&e)|(e&c))&j))&g)&l))&d))|(((((((n&e)|(e&c))|((e|((n|e)&c))&j))&g)|(((((n&e)&c)&j)|((((n&e)|(e&c))|((e|((n|e)&c))&j))&g))&l))|((((((n&e)&c)&j)|(((e|((n|e)&c))|((n|e)&j))&g))|((((n&e)&j)|(((e|((n|e)&c))...

result:

ok 4 lines, tightest: 4722 out of 8202 (4 test cases)

Test #26:

score: 0
Accepted
time: 9ms
memory: 3840kb

input:

4
14
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
(((((((((((g&m)&b)&f)&j)&h)&i)&c)&n)&d)|(((((((((((g&m)&b)|((g&b)&f))|(((g&b)|(((g&m)|(((g|m)|a)&b))&f))&j))|((((g&b)|(((g&m)|((g|m)&b))&f))|((((g&m)|((g|m)&b))|((g|b)&f))&j))&h))&i)&c)&n)|(((((((((g&m)&b)&f)&j)|(((((g&m)&b)&f)|((((g&m)&b)|((g&b)&f))&j))&h))&i)&c)|((((((((g&m)&b)&f)&j)|(((((g&m)...

result:

ok 4 lines, tightest: 4630 out of 8202 (4 test cases)

Test #27:

score: 0
Accepted
time: 8ms
memory: 3840kb

input:

4
14
0000000000000000000000000001001100000000000000110000000000110011000000000011001100000000001100110000000000110011000000000011001100000000001100110000000000110011000000000011001100000000001100110001001100111111001100111111111100110011111111110011001111111111000000000011001100000011001101110000000...

output:

Yes
((((((((((n&g)&i)|(((n&g)|((n|g)&i))&d))|((((((n&g)&i)|(((n&g)|((n|g)&i))&d))|(((((n&g)&i)|(((n&g)|((n|g)&i))&d))|((((n&g)&i)|((n|i)&d))&c))&a))|((((((n&g)&i)|(((n&g)|((n|g)&i))&d))|(((n&i)|((n|i)&d))&c))|(((((n&g)&i)|((n|i)&d))|(((n&i)|((n|i)&d))&c))&a))&j))&e))|((((((n&g)&i)|(((n&g)|((n|g)&i))...

result:

ok 4 lines, tightest: 5123 out of 8202 (4 test cases)

Test #28:

score: 0
Accepted
time: 9ms
memory: 4096kb

input:

4
14
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000001000000000000000000000000000000000000000...

output:

Yes
((((((((((b&l)&a)&j)&k)&f)|(((((((b&l)&a)&j)&k)|((((((b&l)&n)&a)&j)|((((((b&l)|(b&n))&a)&j)|(((((b&l)&n)|(b&a))&j)&e))&k))&f))|((((((b&l)&a)&j)&k)|(((((b&l)&a)&j)|((((((b&l)&n)|(b&a))&j)|((((b&l)|(b&a))&j)&e))&k))&f))&h))&g))|((((((((b&l)&a)&j)&k)|(((((b&l)&a)&j)|(((((b&l)&n)|(b&a))&j)&k))&f))|(...

result:

ok 4 lines, tightest: 4852 out of 8202 (4 test cases)

Test #29:

score: 0
Accepted
time: 5ms
memory: 3968kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((i&n)&a)&m)&d)&l)&f)&o)&c)&h)&g)|(((((((((i&n)&a)&d)&l)&f)&o)&c)&h)&k))|((((((((((((i&n)&a)&m)&d)|(((((i&n)&a)|((n&a)&m))&d)&l))&f)&o)&c)&h)|(((((((((i&n)&a)&d)|(((((i&n)&a)|((n&a)&m))&d)&l))&f)&o)&c)&h)&g))|(((((((((((i&n)&a)&m)&d)&l)&f)&o)&c)|(((((((((i&n)&a)&m)&d)&l)&f)&o)|((((((...

result:

ok 1 lines, tightest: 1529 out of 16394 (1 test case)

Test #30:

score: 0
Accepted
time: 5ms
memory: 3968kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
(((((((((((((k&b)&m)&c)&n)&g)&j)&l)|((((((m&c)&n)|((((b&m)&c)|((m&c)&n))&g))&j)|(((((((k|b)&m)&c)&n)&g)|((((m&c)|(((b&m)|((b|m)&c))&n))|(((m&c)|((m|c)&n))&g))&j))&l))&e))&h)|((((((((((b&m)&c)&n)&g)&j)&l)|((((((m&c)&n)|(((((k|b)&m)&c)|((m&c)&n))&g))&j)|(((((((k&b)&m)&c)&n)|(((m&c)&n)&g))|((((m&c)...

result:

ok 1 lines, tightest: 4213 out of 16394 (1 test case)

Test #31:

score: 0
Accepted
time: 3ms
memory: 3968kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...

output:

Yes
(((((((((((((g&o)&l)&h)&j)&i)&a)&b)|((((((((g&o)&l)&h)&j)&i)|((((((g&o)&l)&h)|((((g&o)|(o&l))&h)&j))&i)&a))&b)&f))|(((((((((g&o)&l)&h)&j)&i)&a)|((((((g&o)&h)&j)&i)|(((((g&o)&h)&j)|((((g&o)&h)|((((g&o)&l)|((o|((g|o)&l))&h))&j))&i))&a))&b))|((((((((g&o)&l)&h)&j)&i)|((((((g&o)&l)&h)|((((g&o)|(o&l))...

result:

ok 1 lines, tightest: 5459 out of 16394 (1 test case)

Test #32:

score: 0
Accepted
time: 5ms
memory: 4224kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000001100000000000000110000001100111111000000000000000000000000000000000000000...

output:

Yes
((((((((((((b&g)&n)&h)&e)&m)|((((((((b&g)&n)&h)&e)|(((((b|g)&n)&h)&e)&m))|((((((b&g)&n)&h)&e)|(((((b&g)|((b|g)&n))&h)&e)&m))&a))|(((((((b&g)&n)&h)&e)|(((((b|g)&n)&h)&e)&m))|((((((b&g)&n)&h)&e)|(((((b&g)&n)&h)|((((b&g)|((b|g)&n))&h)&e))&m))&a))&o))&d))|(((((((((b&g)&n)&h)&e)|((((b&n)&h)&e)&m))|((...

result:

ok 1 lines, tightest: 11173 out of 16394 (1 test case)

Test #33:

score: 0
Accepted
time: 5ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((m&h)&a)&i)&b)&e)|((((((m&h)&a)&i)&b)|(((((m&h)&a)&i)|((((m&h)&a)|(((m&h)|(h&a))&i))&b))&e))&f))|(((((((m&h)&a)&i)&b)&e)|((((((m&h)&a)&i)&b)|(((((m&h)&a)&i)|((((m&h)&a)|(((m&h)|((m|h)&a))&i))&b))&e))&f))&g))&o)&d)|(((((((((m&h)&a)&i)&b)&e)&f)&o)|(((((((((m&h)&a)&i)&b)&e)&f)&g)|(((((...

result:

ok 1 lines, tightest: 5724 out of 16394 (1 test case)

Test #34:

score: 0
Accepted
time: 4ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010100000000000000000000000001010101000000000000000000000000000000000000000...

output:

Yes
(((((((((((((m&o)&j)&h)&b)&g)&e)|(((((m&j)&h)&g)&e)&f))|((((((((m&o)&j)&h)|(((m&j)&h)&b))&g)&e)|(((((((m&j)&h)|((((m&o)|(m&j))&h)&b))&g)|((((((m&o)&j)&h)&b)|((((m&j)&h)|((((m&o)|(m&j))&h)&b))&g))&c))&e)&f))&l))|((((((((((m&o)&j)&h)&b)&g)&c)|(((((((m&o)&j)&h)&b)|(((((m&o)|(m&j))&h)|((((m&o)|((m|o...

result:

ok 1 lines, tightest: 6712 out of 16394 (1 test case)

Test #35:

score: 0
Accepted
time: 375ms
memory: 3840kb

input:

65536
7
00000000000000010000000100000101000000000001011100000101010111110000000100000001000001110001011100000101001101110011011111111111
7
00000000000000010000000000010111000000000000011100000001011111110000000100000001000000110011011100010101001101110011111111111111
7
000000000000000000000001000100...

output:

Yes
((((((a&d)&b)&c)|((((a&d)|(a&b))&c)&e))|(((((a&d)&b)|(((a&d)|(d&b))&c))|(((a&d)|((a|d)&c))&e))&f))|(((((a&b)&c)|((((a&d)&b)|((a|b)&c))&e))|((((d&b)|((a|((a|d)&b))&c))|(((d|b)|(((a|d)|b)&c))&e))&f))&g))
Yes
((((((d&b)&c)&a)|((((d&b)&c)|((d&c)&a))&f))|((((b&c)&a)|(((d&b)|((b|c)&a))&f))&g))|((((((d...

result:

ok 65536 lines, tightest: 70 out of 74 (65536 test cases)

Test #36:

score: 0
Accepted
time: 109ms
memory: 3840kb

input:

1024
10
0000000000000000000000000000000000000000000000000000000000000011000000000000000000000001000001110000000000000111000101010111011100000000000000000000000000000111000000010001011100010011000101110000000100000001000001110001011100000101011111110101111111111111000000000000000100000000000100010000...

output:

Yes
(((((((((h&b)&g)|(((h&b)|(h&g))&d))&e)&j)|((((((h&b)&g)|(((h&b)|(b&g))&d))&e)|(((((h&b)|((h|b)&g))&d)|(((h&b)|((h|b)&d))&e))&j))&c))|(((((((h&b)&g)&d)&e)|(((((h&b)|(h&g))&d)|((((h&b)|(h&g))|((b|g)&d))&e))&j))|(((((h&b)&g)|((((h|b)&g)|((h|g)&d))&e))|(((((h|b)&g)|(((h&b)|((h|b)&g))&d))|(((b|((h|b)...

result:

ok 1024 lines, tightest: 435 out of 522 (1024 test cases)

Test #37:

score: 0
Accepted
time: 33ms
memory: 3840kb

input:

64
12
000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000101110000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000010000000100010101000101110111111100000000000000000000000000000001000000...

output:

Yes
(((((((((((d&b)&g)&f)&l)|(((((d&b)&g)&f)|((((d&b)|(b&g))&f)&l))&a))&j)|(((((((d&b)&g)&f)|((((d&b)&g)|((d&b)&f))&l))&a)|((((((d&b)&g)&f)|((((d&b)&g)|(((d&b)|(b&g))&f))&l))|(((((d&b)&g)|((d&b)&f))|((((d&b)|(b&g))|((d|((d|b)&g))&f))&l))&a))&j))&e))|((((((((d&b)&g)&f)&l)|(((((d&b)&g)&f)|((((d&b)&g)|...

result:

ok 64 lines, tightest: 1534 out of 2058 (64 test cases)

Test #38:

score: 0
Accepted
time: 32ms
memory: 3840kb

input:

64
12
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000...

output:

Yes
(((((((((((k&j)&e)&l)&h)&g)&a)|((((((k&j)&e)&l)&h)&g)&c))|((((((((k|j)&e)&l)&h)&g)&a)|(((((((k&j)&e)&l)&h)|((((k&j)&e)&h)&g))|((((((k&j)&e)|(((k&j)|(j&e))&l))&h)|(((((k&j)|(k&e))&l)|((((k&j)|((k|j)&e))|((k|e)&l))&h))&g))&a))&c))&d))|(((((((((k&j)&e)&l)&h)&g)|((((((k&j)&e)|(((k&j)|(k&e))&l))&h)&g...

result:

ok 64 lines, tightest: 1330 out of 2058 (64 test cases)

Test #39:

score: 0
Accepted
time: 32ms
memory: 3840kb

input:

64
12
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000...

output:

Yes
(((((((((((b&l)&f)&j)&c)&e)&a)|(((((((b&l)&f)&j)|((((b&l)|((b|l)&f))&j)&c))&e)&a)&k))&g)|(((((((((b&l)&f)&j)|((((b&l)&f)|(((b&l)|(b&f))&j))&c))&e)&a)&k)|(((((((b&f)&j)&c)&e)&a)|(((((((b&l)&f)&j)|(((l&f)&j)&c))&e)|((((((b&l)&f)&j)|((((b|l)&f)&j)&c))|(((((b&l)&f)|(((b&l)|(b&f))&j))|((((b&l)&f)|((l...

result:

ok 64 lines, tightest: 922 out of 2058 (64 test cases)

Test #40:

score: 0
Accepted
time: 9ms
memory: 3968kb

input:

4
14
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000010111000000000000000000000000000000000000000...

output:

Yes
(((((((((((((m&f)&c)&l)&j)&k)&i)|(((((((m&f)&c)&l)&j)&k)|(((((f&c)&l)&j)&k)&i))&b))|((((((((m&f)&c)&l)&j)&k)|(((((m&f)&c)&l)&k)&i))|(((((((m&f)&c)&l)&j)|(((((m&f)&c)&l)|(((m&f)&c)&j))&k))|((((((m&f)&c)|((m&f)&l))&j)|((((m&f)&c)|(((f&c)|(((m|f)|c)&l))&j))&k))&i))&b))&n))|(((((((((m&f)&c)|((f&c)&l...

result:

ok 4 lines, tightest: 5471 out of 8202 (4 test cases)

Test #41:

score: 0
Accepted
time: 9ms
memory: 3968kb

input:

4
14
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000...

output:

Yes
(((((((((((((e&g)&i)&a)&j)|((((g&i)&a)&j)&k))&m)&b)&f)|(((((((((e&g)&i)&a)&j)&k)|((((((e&g)&i)&a)|((((e&g)&i)|(((e&g)|(e&i))&a))&j))&k)&m))&b)|((((((((e&g)&i)&a)&j)|(((((e&g)&i)&a)|((((e&g)&i)|(((e&g)|((e|g)&i))&a))&j))&k))&m)|(((((((e&g)&i)&a)&j)|(((((e&g)&i)&a)|((((e&g)&i)|((g&i)&a))&j))&k))|(...

result:

ok 4 lines, tightest: 4895 out of 8202 (4 test cases)

Test #42:

score: 0
Accepted
time: 4ms
memory: 3968kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000100000001000000000000000000000000000000000000000...

output:

Yes
((((((((((((((m&e)&g)&k)&b)&f)|((((((m&e)|(m&g))&k)&b)&f)&c))&a)|((((((((m&e)&g)&k)&b)&f)|((((((m&e)&g)&k)|((((m&e)|(m&g))&k)&b))&f)&c))|(((((((m&e)&g)&k)|((((m&e)|((m|e)&g))&k)&b))&f)|((((((m&e)&g)&k)|((((m&e)&g)|((e&g)&k))&b))|(((((m&e)&g)|(((m&e)|(e&g))&k))|((((m&e)|(m&g))|(((m&e)|((m|e)&g))&...

result:

ok 1 lines, tightest: 10445 out of 16394 (1 test case)

Test #43:

score: 0
Accepted
time: 5ms
memory: 4224kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((n&o)&h)&a)&g)&j)|((((((n&o)|(n&h))&a)&g)&j)&d))&m)&l)|(((((((((n&o)&h)&a)&g)&j)&d)|(((((((n&o)&h)&a)&g)&j)|((((((n&o)&h)&a)&g)|(((((n&o)&h)&a)|(((o&h)&a)&g))&j))&d))&m))|((((((((n&o)&h)&a)&g)&j)|((((((n&o)&h)&a)&g)|(((((n&o)&h)|((o&h)&a))&g)&j))&d))|(((((((n&o)&h)&a)&g)|(((((n&o)|(...

result:

ok 1 lines, tightest: 10161 out of 16394 (1 test case)

Test #44:

score: 0
Accepted
time: 4ms
memory: 4096kb

input:

1
15
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

Yes
((((((((((((((a&d)&k)&f)&g)&m)&j)&b)&o)|(((((((((a&d)&k)&f)&g)&m)&j)&b)|((((((((a&d)&k)&f)&g)&m)&j)|(((((((a&d)&k)&f)&g)&m)|((((((a&d)&k)&f)&g)|(((((a&d)&k)&f)|((((a|d)&k)&f)&g))&m))&j))&b))&o))&c))|((((((((((a&d)&k)&f)&g)&m)&j)&b)|((((((((a&d)&k)&f)&g)&m)&j)|(((((((a&d)&k)&f)&g)&m)|((((((a&d)&k...

result:

ok 1 lines, tightest: 8394 out of 16394 (1 test case)

Extra Test:

score: 0
Extra Test Passed