Submission #749031

#	Time	Username	Problem	Language	Result	Execution time	Memory
749031		model_code	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	5476 ms	1443052 KiB

abc

#include "abc.h"
#include <bits/stdc++.h>
using namespace std;

const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

static int l, la, lb;
static int* operations;
static int (*operands)[2];
static int (*outputs)[16];

int makeGate(int op, int x0, int x1) {
    operations[l] = op;
    operands[l][0] = x0;
    operands[l][1] = x1;
    return l++;
}

struct Gate;
using GatePtr = shared_ptr<Gate>;

struct Gate {
    int id;
    Gate() : id(-1) { }
    virtual ~Gate() { }
    virtual int materialize() = 0;
};

struct InputGate : Gate {
    int from, index;
    InputGate(int from, int index) : from(from), index(index) { }
    int materialize() override {
        if (id != -1)
            return id;
        return id = from * la + index;
    }
};

struct ComputeGate : Gate {
    GatePtr inputs[2];
    int op;
    ComputeGate(const GatePtr& a, const GatePtr& b, int op) : op(op) {
        inputs[0] = a;
        inputs[1] = b;
    }
    int materialize() override {
        if (id != -1)
            return id;
        return id = makeGate(op, inputs[0]->materialize(), inputs[1]->materialize());
    }
};

struct NotGate : Gate {
    GatePtr input;
    NotGate(const GatePtr& input) : input(input) { }
    int materialize() override {
        if (id != -1)
            return id;
        return id = makeGate(OP_NOT_X0, input->materialize(), 0);
    }
};

struct ConstGate : Gate {
    bool value;
    ConstGate(bool value) : value(value) { }
    int materialize() override {
        if (id != -1)
            return id;
        return id = makeGate(value * OP_ONE, 0, 0);
    }
};

struct UndefinedGate : Gate {
    int materialize() override {
        if (id != -1)
            return id;
        return id = makeGate(OP_ZERO, 0, 0);
    }
};

static int dual(int op) {
    return op & 9 | (op & 2) << 1 | (op & 4) >> 1;
}

static GatePtr undefinedGate() {
    static GatePtr undefined = make_shared<UndefinedGate>();
    return undefined;
}

static GatePtr constGate(bool value) {
    static GatePtr consts[2] = { make_shared<ConstGate>(false), make_shared<ConstGate>(true) };
    return consts[value];
}

static GatePtr notGate(const GatePtr& input) {
    if (auto c = dynamic_cast<ConstGate*>(input.get()))
        return constGate(!c->value);
    if (auto u = dynamic_cast<UndefinedGate*>(input.get()))
        return undefinedGate();
    if (auto n = dynamic_cast<NotGate*>(input.get()))
        return n->input;
    return make_shared<NotGate>(input);
}

static map<tuple<GatePtr, GatePtr, int>, GatePtr> computeGateCache;
static GatePtr computeGate(const GatePtr& a, const GatePtr& b, int op) {
    /*if (op == OP_ZERO || op == OP_ONE)
        return constGate(op == OP_ONE);
    if (op == OP_X0)
        return a;
    if (op == OP_X1)
        return b;
    if (op == OP_NOT_X0)
        return notGate(a);
    if (op == OP_NOT_X1)
        return notGate(b);
    
    if (NotGate* na = dynamic_cast<NotGate*>(a.get()))
        return computeGate(b, a, dual(op));
    if (NotGate* nb = dynamic_cast<NotGate*>(b.get()))
        return computeGate(a, nb->input, op >> 2 | (op & 3) << 2);

    UndefinedGate* ua = dynamic_cast<UndefinedGate*>(a.get()), *ub = dynamic_cast<UndefinedGate*>(b.get());
    if (ua && ub)
        return undefinedGate();
    if (ua)
        return computeGate(b, a, dual(op));
    if (ub) {
        int cnt = __builtin_popcount(op);
        if (cnt >= 3)
            return constGate(1);
        if (cnt <= 1)
            return constGate(0);
        return a;
    }

    ConstGate* ca = dynamic_cast<ConstGate*>(a.get()), *cb = dynamic_cast<ConstGate*>(b.get());
    if (ca && cb)
        return constGate(op >> (ca->value | cb->value << 1) & 1);
    if (ca)
        return computeGate(b, a, dual(op));
    if (cb) {
        int x = op >> (cb->value << 1) & 3;
        if (x == 1)
            return notGate(a);
        if (x == 2)
            return a;
        return constGate(x == 3);
    }*/

    /*auto& result = computeGateCache[make_tuple(a, b, op)];
    if (result)
        return result;
    result = make_shared<ComputeGate>(a, b, op);
    return result;*/
    return make_shared<ComputeGate>(a, b, op);
}

static GatePtr inputGate(int from, int index) {
    return make_shared<InputGate>(from, index);
}

struct Bit {
    GatePtr gate;
    Bit() : gate(undefinedGate()) { }
    explicit Bit(bool value) : gate(constGate(value)) { }
    Bit(const GatePtr& gate) : gate(gate) { }
};
static Bit operator&(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_AND);
}
static Bit operator|(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_OR);
}
static Bit operator^(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_XOR);
}
static Bit& operator^=(Bit& a, const Bit& b) {
    a = a ^ b;
    return a;
}
static Bit operator~(const Bit& a) {
    return notGate(a.gate);
}
static Bit operator==(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_EQUAL);
}
static Bit operator!=(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_XOR);
}
static Bit operator>=(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_GEQ);
}
static Bit operator<=(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_LEQ);
}
static Bit operator>(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_GREATER);
}
static Bit operator<(const Bit& a, const Bit& b) {
    return computeGate(a.gate, b.gate, OP_LESS);
}

struct Integer : vector<Bit> {
    using vector<Bit>::vector;
};
static Integer operator&(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Integer result;
    for (int i = 0; i < a.size(); i++)
        result.push_back(a[i] & b[i]);
    return result;
}
static Integer operator|(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Integer result;
    for (int i = 0; i < a.size(); i++)
        result.push_back(a[i] | b[i]);
    return result;
}
static Integer operator^(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Integer result;
    for (int i = 0; i < a.size(); i++)
        result.push_back(a[i] ^ b[i]);
    return result;
}
static Integer operator~(const Integer& a) {
    Integer result;
    for (int i = 0; i < a.size(); i++)
        result.push_back(~a[i]);
    return result;
}
static Integer operator+(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Integer result;
    Bit carry(false);
    for (int i = 0; i < a.size(); i++) {
        Bit x = a[i] ^ b[i];
        result.push_back(x ^ carry);
        carry = (a[i] & b[i]) | (x & carry);
    }
    return result;
}
static Integer& operator+=(Integer& a, const Integer& b) {
    return a = a + b;
}
static Bit operator==(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Bit result(true);
    for (int i = 0; i < a.size(); i++)
        result = result & (a[i] == b[i]);
    return result;
}
static Bit operator!=(const Integer& a, const Integer& b) {
    return ~(a == b);
}
static Bit operator<(const Integer& a, const Integer& b) {
    assert(a.size() == b.size());
    Bit result(false);
    for (int i = 0; i < a.size(); i++)
        result = (a[i] < b[i]) | ((a[i] == b[i]) & result);
    return result;
}
static Bit operator>(const Integer& a, const Integer& b) {
    return b < a;
}
static Bit operator<=(const Integer& a, const Integer& b) {
    return ~(a > b);
}
static Bit operator>=(const Integer& a, const Integer& b) {
    return ~(a < b);
}
static Bit inputBit(int from, int index) {
    return Bit(inputGate(from, index));
}
static Integer inputInteger(int from, int index, int size) {
    Integer result;
    for (int i = 0; i < size; i++)
        result.push_back(inputBit(from, index + i));
    return result;
}
static Integer zeroInteger(int size) {
    Integer result;
    for (int i = 0; i < size; i++)
        result.push_back(Bit(false));
    return result;
}
static Integer undefinedInteger(int size) {
    Integer result;
    for (int i = 0; i < size; i++)
        result.push_back(Bit());
    return result;
}
static int materialize(const Bit& bit) {
    return bit.gate->materialize();
}
static vector<int> materialize(const Integer& integer) {
    vector<int> result;
    for (int i = 0; i < integer.size(); i++)
        result.push_back(materialize(integer[i]));
    return result;
}
static void condSwap(const Bit& cond, Bit& a, Bit& b) {
    Bit x = a ^ b;
    a ^= (x & cond);
    b ^= (x & cond);
}
static void condSwap(const Bit& cond, Integer& a, Integer& b) {
    assert(a.size() == b.size());
    for (int i = 0; i < a.size(); i++)
        condSwap(cond, a[i], b[i]);
}
static void condAssign(const Bit& cond, Integer& a, const Integer& b) {
    Integer bb = b;
    condSwap(cond, a, bb);
}

struct Element {
    Integer src;    // 19b
    Integer dst;    // 19b
    Integer weight; // 16b
    Bit isEdge;
    // 19+19+16+1=55b
};
static void condSwap(const Bit& cond, Element& a, Element& b) {
    condSwap(cond, a.src, b.src);
    condSwap(cond, a.dst, b.dst);
    condSwap(cond, a.weight, b.weight);
    condSwap(cond, a.isEdge, b.isEdge);
}

static int charsToInt(const char c[5]) {
    int result = 0;
    for (int i = 0; i < 4; i++) {
        if (!c[i])
            break;
        result = result * 26 + (c[i] - 'a') + 1;
    }
    return result;
}

static vector<bool> switchGenerateInv(vector<int> a) {
    // permute `a` to [0, 1, ..., n - 1]
    int n = a.size();
    // cout << "switchGenerateInv " << n << endl;
    if (n <= 1)
        return vector<bool>();
    
    vector<bool> upHold((n + 1) / 2), downHold((n + 1) / 2);
    if (n % 2) {
        // upHold[n / 2 * 2] = true;
        downHold[a[n - 1] >= n / 2 ? a[n - 1] - n / 2 : a[n - 1]] = true;
    }
    
    vector<bool> trace(n / 2), sure(n / 2);

    int cnt = n / 2;
    while (cnt > 0) {
        // cout << cnt << endl;
        bool ok = false;
        for (int i = 0; i < n / 2; i++)
            if (!sure[i]) {
                int col = a[i] >= n / 2 ? a[i] - n / 2 : a[i];
                int ncol = a[i + n / 2] >= n / 2 ? a[i + n / 2] - n / 2 : a[i + n / 2];
                if (upHold[col] || downHold[ncol]) {
                    downHold[col] = 1;
                    upHold[ncol] = 1;
                    trace[i] = 1;
                    swap(a[i], a[i + n / 2]);
                    sure[i] = 1;
                    ok = true;
                    --cnt;
                }
                else if (downHold[col] || upHold[ncol]) {
                    upHold[col] = 1;
                    downHold[ncol] = 1;
                    trace[i] = 0;
                    sure[i] = 1;
                    ok = true;
                    --cnt;
                }
            }
        if (ok)
            continue;
        for (int i = 0; i < n / 2; i++)
            if (!sure[i]) {
                int col = a[i] >= n / 2 ? a[i] - n / 2 : a[i];
                int ncol = a[i + n / 2] >= n / 2 ? a[i + n / 2] - n / 2 : a[i + n / 2];
                upHold[col] = 1;
                downHold[ncol] = 1;
                trace[i] = 0;
                sure[i] = 1;
                --cnt;
                break;
            }
    }
    // cout << cnt << endl;

    vector<int> a1(a.begin(), a.begin() + n / 2);
    vector<int> a2(a.begin() + n / 2, a.end());
    transform(a1.begin(), a1.end(), a1.begin(), [&](int x) { return x >= n / 2 ? x - n / 2 : x; });
    transform(a2.begin(), a2.end(), a2.begin(), [&](int x) { return x >= n / 2 ? x - n / 2 : x; });
    auto trace1 = switchGenerateInv(a1);
    auto trace2 = switchGenerateInv(a2);
    trace.insert(trace.end(), trace1.begin(), trace1.end());
    trace.insert(trace.end(), trace2.begin(), trace2.end());
    vector<bool> trace3(n / 2);
    for (int i = 0; i < n / 2; i++)
        if (a[i] >= n / 2)
            trace3[a[i] - n / 2] = 1;
    trace.insert(trace.end(), trace3.begin(), trace3.end());
    return trace;
}

static vector<bool> switchGenerate(const vector<int>& a) {
    // permute [0, 1, ..., n - 1] to `a`
    int n = a.size();
    vector<int> invA(n);
    for (int i = 0; i < n; i++)
        invA[a[i]] = i;
    return switchGenerateInv(invA);
}


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs[]
) {
    int l = 0;
    auto addBit = [&](bool bit) {
        outputs[l++] = bit;
    };
    auto addInteger = [&](int integer, int size) {
        for (int i = 0; i < size; i++)
            addBit(integer >> i & 1);
    };

    vector<tuple<int, unsigned short, int>> v;
    for (int i = 0; i < n; i++)
        v.push_back(make_tuple(charsToInt(names[i]), numbers[i], i));
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        addInteger(get<0>(v[i]), 19);
        addInteger(get<0>(v[i]), 19);
        addInteger(get<1>(v[i]), 16);
        addBit(false);
    }

    vector<int> p;
    for (int i = 0; i < n; i++)
        p.push_back(get<2>(v[i]));
    // for (int i = 0; i < n; i++)
    //     cout << p[i] << " ";
    // cout << endl;
    auto trace = switchGenerateInv(p);
    for (bool bit : trace)
        addBit(bit);

    return l;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs[]
) {
    int l = 0;
    auto addBit = [&](bool bit) {
        outputs[l++] = bit;
    };
    auto addInteger = [&](int integer, int size) {
        for (int i = 0; i < size; i++)
            addBit(integer >> i & 1);
    };

    vector<pair<int, int>> v;
    for (int i = 0; i < m; i++)
        v.push_back(make_pair(charsToInt(senders[i]), charsToInt(recipients[i])));
    sort(v.begin(), v.end());

    vector<tuple<int, int, int>> w;
    for (int i = 0; i < m; i++)
        w.emplace_back(v[i].first, v[i].second, i);
    sort(w.begin(), w.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
        return get<1>(a) < get<1>(b);
    });
    vector<int> p;
    for (int i = 0; i < m; i++)
        p.push_back(get<2>(w[i]));
    vector<bool> trace = switchGenerate(p);

    for (int i = 0; i < m; i++) {
        addInteger(v[i].first, 19);
        addInteger(v[i].second, 19);
        addInteger(0, 16);
        addBit(true);
    }

    for (bool bit : trace)
        addBit(bit);
    return l;
}

template <typename F>
static void buildMergeNetworkImpl(const F& yield, int i, int x, int j, int k, int r) {
    int step = r * 2, m = x - i, n = k - j;
    if (m <= 0 || n <= 0)
        return;
    if (m <= r && n <= r) {
        yield(i, j);
        return;
    }
    buildMergeNetworkImpl(yield, i, x, j, k, step);
    buildMergeNetworkImpl(yield, i + r, x, j + r, k, step);
    for (i += r, x -= r; i < x; i += step)
        yield(i, i + r);
    if (i < x + r) {
        yield(i, j);
        j += r;
    }
    for (k -= r; j < k; j += step)
        yield(j, j + r);
}

template <typename F>
static void buildMergeNetworkImpl(const F& yield, int l, int m, int r) {
    auto myYield = [&](int x, int y) {
        if (x >= l && x < r && y >= l && y < r)
            yield(x, y);
    };
    buildMergeNetworkImpl(myYield, l, m, m, r, 1);
}

static vector<pair<int, int>> buildMergeNetwork(int n1, int n2) {
    int mx = max(n1, n2), n = n1 + n2;
    vector<pair<int, int>> ret;
    buildMergeNetworkImpl([&](int x, int y) {
        if (x >= 0 && x < n && y >= 0 && y < n)
            ret.emplace_back(x, y);
    }, n1 - mx, n1, n1 + mx);
    return ret;
}

template <typename Less>
static void sortElements(vector<Element>& elements, Less less) {
    // TODO: optimize
    for (int i = 0; i < elements.size(); i++)
        for (int j = i + 1; j < elements.size(); j++)
            condSwap(less(elements[j], elements[i]), elements[i], elements[j]);
}

template <typename Less>
static vector<tuple<int, int, Bit>> mergeElements(vector<Element>& elements, int mid, Less less) {
    vector<pair<int, int>> network = buildMergeNetwork(mid, elements.size() - mid);
    vector<tuple<int, int, Bit>> ret;
    for (auto& p : network) {
        Bit cond = less(elements[p.second], elements[p.first]);
        condSwap(cond, elements[p.first], elements[p.second]);
        ret.emplace_back(p.first, p.second, cond);
    }
    return ret;
}

static void undoMergeElements(vector<Element>& elements, const vector<tuple<int, int, Bit>>& operations) {
    for (int i = operations.size() - 1; i >= 0; i--) {
        int x, y;
        Bit cond;
        tie(x, y, cond) = operations[i];
        condSwap(cond, elements[x], elements[y]);
    }
}

template <typename F>
static void buildSwitchNetworkImpl(const F& yield, int l, int r) {
    if (r - l <= 1)
        return;
    int m = (l + r) / 2;
    auto preOrPost = [&]() {
        for (int i = l, j = m; i < m; i++, j++)
            yield(i, j);
    };
    preOrPost();
    buildSwitchNetworkImpl(yield, l, m);
    buildSwitchNetworkImpl(yield, m, r);
    preOrPost();
}

static vector<pair<int, int>> buildSwitchNetwork(int n) {
    vector<pair<int, int>> ret;
    buildSwitchNetworkImpl([&](int x, int y) {
        if (x >= 0 && x < n && y >= 0 && y < n)
            ret.emplace_back(x, y);
    }, 0, n);
    return ret;
}

static void permuteElements(vector<Element>& elements, const vector<Bit>& trace) {
    vector<pair<int, int>> network = buildSwitchNetwork(elements.size());
    assert(network.size() == trace.size());
    for (int i = 0; i < network.size(); i++)
        condSwap(trace[i], elements[network[i].first], elements[network[i].second]);
}

static void undoPermuteElements(vector<Element>& elements, const vector<Bit>& trace) {
    vector<pair<int, int>> network = buildSwitchNetwork(elements.size());
    assert(network.size() == trace.size());
    for (int i = network.size() - 1; i >= 0; i--)
        condSwap(trace[i], elements[network[i].first], elements[network[i].second]);
}

// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs[][16]
) {
    ::l = la + lb;
    ::la = la;
    ::lb = lb;
    ::operations = operations;
    ::operands = operands;
    ::outputs = outputs;

    // cout << la << ' ' << lb << endl;
    
    int n = 0;
    while (n * 55 + buildSwitchNetwork(n).size() < la)
        n++;
    int m = 0;
    while (m * 55 + buildSwitchNetwork(m).size() < lb)
        m++;
    // cout << n << ' ' << m << endl;
    assert(m * 55 + buildSwitchNetwork(m).size() == lb);
    int nm = n + m;
    vector<Element> elements;
    for (int i = 0; i < n; i++) {
        Element element;
        element.src = inputInteger(0, i * 55, 19);
        element.dst = inputInteger(0, i * 55 + 19, 19);
        element.weight = inputInteger(0, i * 55 + 38, 16);
        element.isEdge = inputBit(0, i * 55 + 54);
        elements.push_back(element);
    }
    for (int i = 0; i < m; i++) {
        Element element;
        element.src = inputInteger(1, i * 55, 19);
        element.dst = inputInteger(1, i * 55 + 19, 19);
        element.weight = inputInteger(1, i * 55 + 38, 16);
        element.isEdge = inputBit(1, i * 55 + 54);
        elements.push_back(element);
    }
    vector<Bit> perm;
    for (int i = 0; i < lb - m * 55; i++)
        perm.push_back(inputBit(1, m * 55 + i));
        
    vector<Bit> permA;
    for (int i = 0; i < la - n * 55; i++)
        permA.push_back(inputBit(0, n * 55 + i));

    auto trace = mergeElements(elements, n, [](const Element& a, const Element& b) {
        return (a.src < b.src) | ((a.src == b.src) & (a.isEdge < b.isEdge));
    });
    Integer w = undefinedInteger(16);
    for (int i = 0; i < nm; i++) {
        condAssign(~elements[i].isEdge, w, elements[i].weight);
        condAssign(elements[i].isEdge, elements[i].weight, w);
    }
    undoMergeElements(elements, trace);

    vector<Element> tmp;
    for (int i = 0; i < m; i++)
        tmp.push_back(elements[n + i]);
    permuteElements(tmp, perm);
    for (int i = 0; i < m; i++)
        elements[n + i] = tmp[i];
    trace = mergeElements(elements, n, [](const Element& a, const Element& b) {
        return (a.dst < b.dst) | ((a.dst == b.dst) & (a.isEdge > b.isEdge));
    });
    Integer zero = zeroInteger(16), sum = zero;
    for (int i = 0; i < nm; i++) {
        condAssign(elements[i].isEdge, sum, sum + elements[i].weight);
        condAssign(~elements[i].isEdge, elements[i].weight, sum);
        condAssign(~elements[i].isEdge, sum, zero);
    }
    undoMergeElements(elements, trace);

    tmp.clear();
    for (int i = 0; i < n; i++)
        tmp.push_back(elements[i]);
    permuteElements(tmp, permA);
    for (int i = 0; i < n; i++)
        elements[i] = tmp[i];

    for (int i = 0; i < n; i++) {
        vector<int> w = materialize(elements[i].weight);
        memcpy(outputs[i], w.data(), w.size() * sizeof(int));
    }

    return ::l;
}

Compilation message (stderr)

abc.cpp: In function 'int dual(int)':
abc.cpp:97:15: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   97 |     return op & 9 | (op & 2) << 1 | (op & 4) >> 1;
      |            ~~~^~~
abc.cpp: In function 'GatePtr notGate(const GatePtr&)':
abc.cpp:113:14: warning: unused variable 'u' [-Wunused-variable]
  113 |     if (auto u = dynamic_cast<UndefinedGate*>(input.get()))
      |              ^
abc.cpp: In function 'Integer operator&(const Integer&, const Integer&)':
abc.cpp:225:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator|(const Integer&, const Integer&)':
abc.cpp:232:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator^(const Integer&, const Integer&)':
abc.cpp:239:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator~(const Integer&)':
abc.cpp:245:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Integer operator+(const Integer&, const Integer&)':
abc.cpp:253:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Bit operator==(const Integer&, const Integer&)':
abc.cpp:266:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  266 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'Bit operator<(const Integer&, const Integer&)':
abc.cpp:276:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'std::vector<int> materialize(const Integer&)':
abc.cpp:315:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  315 |     for (int i = 0; i < integer.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
abc.cpp: In function 'void condSwap(const Bit&, Integer&, Integer&)':
abc.cpp:326:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Bit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  326 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
abc.cpp: In function 'void permuteElements(std::vector<Element>&, const std::vector<Bit>&)':
abc.cpp:625:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  625 |     for (int i = 0; i < network.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
abc.cpp: In function 'int circuit(int, int, int*, int (*)[2], int (*)[16])':
abc.cpp:655:50: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  655 |     while (n * 55 + buildSwitchNetwork(n).size() < la)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
abc.cpp:658:50: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  658 |     while (m * 55 + buildSwitchNetwork(m).size() < lb)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from abc.cpp:2:
abc.cpp:661:50: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  661 |     assert(m * 55 + buildSwitchNetwork(m).size() == lb);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
abc.cpp: At global scope:
abc.cpp:629:13: warning: 'void undoPermuteElements(std::vector<Element>&, const std::vector<Bit>&)' defined but not used [-Wunused-function]
  629 | static void undoPermuteElements(vector<Element>& elements, const vector<Bit>& trace) {
      |             ^~~~~~~~~~~~~~~~~~~
abc.cpp:286:12: warning: 'Bit operator>=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  286 | static Bit operator>=(const Integer& a, const Integer& b) {
      |            ^~~~~~~~
abc.cpp:283:12: warning: 'Bit operator<=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  283 | static Bit operator<=(const Integer& a, const Integer& b) {
      |            ^~~~~~~~
abc.cpp:270:12: warning: 'Bit operator!=(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  270 | static Bit operator!=(const Integer& a, const Integer& b) {
      |            ^~~~~~~~
abc.cpp:260:17: warning: 'Integer& operator+=(Integer&, const Integer&)' defined but not used [-Wunused-function]
  260 | static Integer& operator+=(Integer& a, const Integer& b) {
      |                 ^~~~~~~~
abc.cpp:243:16: warning: 'Integer operator~(const Integer&)' defined but not used [-Wunused-function]
  243 | static Integer operator~(const Integer& a) {
      |                ^~~~~~~~
abc.cpp:236:16: warning: 'Integer operator^(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  236 | static Integer operator^(const Integer& a, const Integer& b) {
      |                ^~~~~~~~
abc.cpp:229:16: warning: 'Integer operator|(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  229 | static Integer operator|(const Integer& a, const Integer& b) {
      |                ^~~~~~~~
abc.cpp:222:16: warning: 'Integer operator&(const Integer&, const Integer&)' defined but not used [-Wunused-function]
  222 | static Integer operator&(const Integer& a, const Integer& b) {
      |                ^~~~~~~~
abc.cpp:209:12: warning: 'Bit operator<=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
  209 | static Bit operator<=(const Bit& a, const Bit& b) {
      |            ^~~~~~~~
abc.cpp:206:12: warning: 'Bit operator>=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
  206 | static Bit operator>=(const Bit& a, const Bit& b) {
      |            ^~~~~~~~
abc.cpp:203:12: warning: 'Bit operator!=(const Bit&, const Bit&)' defined but not used [-Wunused-function]
  203 | static Bit operator!=(const Bit& a, const Bit& b) {
      |            ^~~~~~~~
abc.cpp:96:12: warning: 'int dual(int)' defined but not used [-Wunused-function]
   96 | static int dual(int op) {
      |            ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24
• Subtask 6: 6 / 6
• Subtask 7: 18 / 18
• Subtask 8: 10 / 10
• Subtask 9: 6 / 6