Editing Openai/69679fe4-9524-800d-9c74-5c34521fd378 (section)

=== Assistant: cpp ===
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
#include <charconv>
using namespace std;

struct Node {
    int x, y;
    uint8_t f; // truth table code 0..15, bit0=f(0,0)
};

struct FastOutput {
    static constexpr size_t FLUSH_THRESHOLD = 1u << 20; // 1MB
    string buf;
    FastOutput() { buf.reserve(FLUSH_THRESHOLD * 2); }

    inline void flush() {
        if (!buf.empty()) {
            cout.write(buf.data(), (streamsize)buf.size());
            buf.clear();
        }
    }

    inline void ensure() {
        if (buf.size() >= FLUSH_THRESHOLD) flush();
    }

    inline void putChar(char c) {
        buf.push_back(c);
        ensure();
    }

    inline void putStr(const char* s) {
        buf.append(s);
        ensure();
    }

    inline void putInt(int v) {
        char tmp[32];
        auto [ptr, ec] = to_chars(tmp, tmp + 32, v);
        (void)ec;
        buf.append(tmp, ptr - tmp);
        ensure();
    }
};

struct CircuitBuilder {
    int n, k;
    int L; // sources = n + 2k
    vector<Node> nodes; // internal nodes only, id = L + index
    int const0, const1;

    // truth table codes (bit order: f0=f(0,0) is LSB)
    static constexpr uint8_t F_AND = 8;  // 0001
    static constexpr uint8_t F_OR  = 14; // 0111
    static constexpr uint8_t F_XOR = 6;  // 0110
    static constexpr uint8_t F_NOTX = 3; // 1100  -> (~x)
    static constexpr uint8_t F_COPYX = 12; // 0011 -> x
    static constexpr uint8_t F_COPY  = 12;

    CircuitBuilder(int n_, int k_, int reserveInternal = 0)
        : n(n_), k(k_), L(n_ + 2 * k_) {
        nodes.reserve(reserveInternal > 0 ? reserveInternal : 1024);
        // const0 = x XOR x (use source 0)
        const0 = add_gate(0, 0, F_XOR);
        // const1 = NOT(const0)
        const1 = add_gate(const0, const0, F_NOTX);
    }

    inline int add_gate(int x, int y, uint8_t f) {
        nodes.push_back({x, y, f});
        return L + (int)nodes.size() - 1;
    }

    inline int AND(int a, int b) { return add_gate(a, b, F_AND); }
    inline int OR(int a, int b)  { return add_gate(a, b, F_OR); }
    inline int XOR(int a, int b) { return add_gate(a, b, F_XOR); }
    inline int NOT(int a)        { return add_gate(a, a, F_NOTX); }
    inline int COPY(int a)       { return add_gate(a, a, F_COPY); }

    inline int OR_all(const vector<int>& v) {
        if (v.empty()) return const0;
        int r = v[0];
        for (size_t i = 1; i < v.size(); i++) r = OR(r, v[i]);
        return r;
    }

    inline int AND_all(const vector<int>& v) {
        if (v.empty()) return const1;
        int r = v[0];
        for (size_t i = 1; i < v.size(); i++) r = AND(r, v[i]);
        return r;
    }

    inline int EQ(int a, int b) { // XNOR
        int x = XOR(a, b);
        return NOT(x);
    }

    static int ceil_log2(int x) {
        if (x <= 1) return 0;
        int b = 0;
        int p = 1;
        while (p < x) { p <<= 1; b++; }
        return b;
    }

    // Build machine (Alice if isAlice=true, Bob otherwise), return output node id
    int buildMachine(const vector<vector<int>>& adj, bool isAlice) {
        const int B = ceil_log2(n);     // bits for vertex index
        const int T = B;                // iterations
        const int Lstage = B + 2;       // per-iteration: B idx bits + valid + membership
        const int R = T * Lstage;       // scheduled rounds (< k)

        // sources: set bits [0..n-1], transcript bits z[j]=n+j
        vector<int> z(2 * k);
        for (int i = 0; i < 2 * k; i++) z[i] = n + i;

        // stage detection for i in [0..R-1], using marker at position 2i
        vector<int> notZ(2 * k);
        for (int i = 0; i < 2 * k; i++) notZ[i] = NOT(z[i]);

        vector<int> suffixZero(2 * k + 1);
        suffixZero[2 * k] = const1;
        for (int i = 2 * k - 1; i >= 0; i--) {
            suffixZero[i] = AND(notZ[i], suffixZero[i + 1]);
        }

        vector<int> isStage(R, const0);
        if (R > 0) {
            isStage[0] = suffixZero[0]; // stage 0: all zeros
            for (int i = 1; i < R; i++) {
                int marker = z[2 * i];
                int after0 = suffixZero[2 * i + 1];
                isStage[i] = AND(marker, after0);
            }
        }

        // isPos[p] = OR over all stages with same position in iteration
        vector<int> isPos(Lstage, const0);
        for (int p = 0; p < Lstage; p++) {
            vector<int> tmp;
            tmp.reserve(T);
            for (int t = 0; t < T; t++) {
                tmp.push_back(isStage[t * Lstage + p]);
            }
            isPos[p] = OR_all(tmp);
        }

        // isIter[t] one-hot for current iteration t
        vector<int> isIter(T, const0);
        for (int t = 0; t < T; t++) {
            vector<int> tmp;
            tmp.reserve(Lstage);
            for (int p = 0; p < Lstage; p++) tmp.push_back(isStage[t * Lstage + p]);
            isIter[t] = OR_all(tmp);
        }

        // decode x_t bits and y_t bits (each length B)
        vector<vector<int>> xBits(T, vector<int>(B, const0));
        vector<vector<int>> yBits(T, vector<int>(B, const0));
        for (int t = 0; t < T; t++) {
            int baseStage = t * Lstage;
            for (int b = 0; b < B; b++) {
                xBits[t][b] = z[2 * (baseStage + b)];     // Alice output at that stage
                yBits[t][b] = z[2 * (baseStage + b) + 1]; // Bob output
            }
        }

        // valid bits per iteration
        vector<int> validA(T, const0), validB(T, const0);
        for (int t = 0; t < T; t++) {
            int stage = t * Lstage + B;
            validA[t] = z[2 * stage];
            validB[t] = z[2 * stage + 1];
        }

        // equality one-hot: eqX[t][v] = (x_t == v) & validA[t], eqY[t][v] similarly
        vector<vector<int>> eqX(T, vector<int>(n, const0));
        vector<vector<int>> eqY(T, vector<int>(n, const0));
        for (int t = 0; t < T; t++) {
            for (int v = 0; v < n; v++) {
                int eqv = const1;
                for (int b = 0; b < B; b++) {
                    int bitv = ((v >> b) & 1) ? const1 : const0;
                    eqv = AND(eqv, EQ(xBits[t][b], bitv));
                }
                eqX[t][v] = AND(eqv, validA[t]);
            }
            for (int v = 0; v < n; v++) {
                int eqv = const1;
                for (int b = 0; b < B; b++) {
                    int bitv = ((v >> b) & 1) ? const1 : const0;
                    eqv = AND(eqv, EQ(yBits[t][b], bitv));
                }
                eqY[t][v] = AND(eqv, validB[t]);
            }
        }

        // alive sets: alive[0]=all ones, alive[t+1] update
        vector<vector<int>> alive(T + 1, vector<int>(n, const1));
        for (int t = 0; t < T; t++) {
            int bothValid = AND(validA[t], validB[t]);

            // neighX[v]= OR_{u in adj[v]} eqX[t][u]
            vector<int> neighX(n, const0), neighY(n, const0);
            for (int v = 0; v < n; v++) {
                vector<int> tmp;
                tmp.reserve(adj[v].size());
                for (int u : adj[v]) tmp.push_back(eqX[t][u]);
                neighX[v] = OR_all(tmp);

                tmp.clear();
                tmp.reserve(adj[v].size());
                for (int u : adj[v]) tmp.push_back(eqY[t][u]);
                neighY[v] = OR_all(tmp);
            }

            for (int v = 0; v < n; v++) {
                int keep = alive[t][v];
                keep = AND(keep, neighX[v]);
                keep = AND(keep, NOT(neighY[v]));
                keep = AND(keep, NOT(eqX[t][v]));
                keep = AND(keep, NOT(eqY[t][v]));
                keep = AND(keep, bothValid);
                alive[t + 1][v] = keep;
            }
        }

        // aliveCur[v] = selected alive[t] by isIter one-hot
        vector<int> aliveCur(n, const0);
        for (int v = 0; v < n; v++) {
            vector<int> tmp;
            tmp.reserve(T);
            for (int t = 0; t < T; t++) tmp.push_back(AND(isIter[t], alive[t][v]));
            aliveCur[v] = OR_all(tmp);
        }

        // degrees in aliveCur: degBits[v][b]
        vector<vector<int>> degBits(n, vector<int>(B, const0));
        for (int v = 0; v < n; v++) {
            vector<int> deg(B, const0);
            for (int u : adj[v]) {
                int add = aliveCur[u];
                vector<int> next(B, const0);
                int carry = add;
                for (int b = 0; b < B; b++) {
                    int sum = XOR(deg[b], carry);
                    int c2 = AND(deg[b], carry);
                    next[b] = sum;
                    carry = c2;
                }
                deg.swap(next);
            }
            for (int b = 0; b < B; b++) degBits[v][b] = deg[b];
        }

        // candidate[v] = ownSet[v] & aliveCur[v]
        vector<int> candidate(n, const0);
        for (int v = 0; v < n; v++) {
            int own = v; // source id for set membership
            candidate[v] = AND(own, aliveCur[v]);
        }

        // validCur = OR candidate[v]
        int validCur = OR_all(candidate);

        // best selection among candidates: min degree for Alice, max degree for Bob
        vector<int> bestIdxBits(B, const0);
        int bestValid = const0;
        vector<int> bestDeg(B, const0);

        auto ltDeg = [&](const vector<int>& a, const vector<int>& b) -> int {
            // returns 1 if a < b (unsigned)
            int less = const0;
            int equal = const1;
            for (int bi = B - 1; bi >= 0; bi--) {
                int ai = a[bi];
                int bi2 = b[bi];
                int notai = NOT(ai);
                int notbi = NOT(bi2);
                int ai_lt_bi = AND(notai, bi2);
                int ai_gt_bi = AND(ai, notbi);
                less = OR(less, AND(equal, ai_lt_bi));
                equal = AND(equal, NOT(OR(ai_lt_bi, ai_gt_bi)));
            }
            return less;
        };

        auto leDeg = [&](const vector<int>& a, const vector<int>& b) -> int {
            // a <= b  <=> !(b < a)
            int b_lt_a = ltDeg(b, a);
            return NOT(b_lt_a);
        };

        auto geDeg = [&](const vector<int>& a, const vector<int>& b) -> int {
            // a >= b <=> !(a < b)
            int a_lt_b = ltDeg(a, b);
            return NOT(a_lt_b);
        };

        for (int v = 0; v < n; v++) {
            int cand = candidate[v];
            if (isAlice) {
                // update if cand & ( !bestValid | deg[v] < bestDeg )
                int better = ltDeg(degBits[v], bestDeg);
                int take = AND(cand, OR(NOT(bestValid), better));
                bestValid = OR(bestValid, cand);

                for (int b = 0; b < B; b++) {
                    int bitv = ((v >> b) & 1) ? const1 : const0;
                    bestIdxBits[b] = OR(AND(take, bitv), AND(NOT(take), bestIdxBits[b]));
                    bestDeg[b]     = OR(AND(take, degBits[v][b]), AND(NOT(take), bestDeg[b]));
                }
            } else {
                // update if cand & ( !bestValid | deg[v] >= bestDeg )  (ties take later v)
                int betterOrEq = geDeg(degBits[v], bestDeg);
                int take = AND(cand, OR(NOT(bestValid), betterOrEq));
                bestValid = OR(bestValid, cand);

                for (int b = 0; b < B; b++) {
                    int bitv = ((v >> b) & 1) ? const1 : const0;
                    bestIdxBits[b] = OR(AND(take, bitv), AND(NOT(take), bestIdxBits[b]));
                    bestDeg[b]     = OR(AND(take, degBits[v][b]), AND(NOT(take), bestDeg[b]));
                }
            }
        }

        // membership bit for current iteration: opponent vertex in my set
        vector<int> memPerIter(T, const0);
        for (int t = 0; t < T; t++) {
            const auto& oppEq = isAlice ? eqY[t] : eqX[t];
            vector<int> tmp;
            tmp.reserve(n);
            for (int v = 0; v < n; v++) {
                int own = v;
                tmp.push_back(AND(own, oppEq[v]));
            }
            memPerIter[t] = OR_all(tmp);
        }
        int memBit = const0;
        for (int t = 0; t < T; t++) memBit = OR(memBit, AND(isIter[t], memPerIter[t]));

        // output for scheduled stages: index bits / valid / membership
        int outScheduled = const0;
        for (int p = 0; p < B; p++) {
            outScheduled = OR(outScheduled, AND(isPos[p], bestIdxBits[p]));
        }
        outScheduled = OR(outScheduled, AND(isPos[B], validCur));
        outScheduled = OR(outScheduled, AND(isPos[B + 1], memBit));

        // foundOverall = OR of membership transcript bits at all membership stages
        int foundOverall = const0;
        for (int t = 0; t < T; t++) {
            int stage = t * Lstage + (B + 1);
            int a_mem = z[2 * stage];
            int b_mem = z[2 * stage + 1];
            foundOverall = OR(foundOverall, OR(a_mem, b_mem));
        }

        // earlyStage = OR_{i<R} isStage[i]
        int earlyStage = const0;
        for (int i = 0; i < R; i++) earlyStage = OR(earlyStage, isStage[i]);

        // final output: if earlyStage -> outScheduled else foundOverall
        // mux(s, a, b) = (s&a) | (~s&b)
        int out = OR(AND(earlyStage, outScheduled), AND(NOT(earlyStage), foundOverall));

        // ensure sink is last node
        int sink = COPY(out);
        return sink;
    }
};

static const char* FSTR[16] = {
    "0000","1000","0100","1100",
    "0010","1010","0110","1110",
    "0001","1001","0101","1101",
    "0011","1011","0111","1111"
};

static void printMachine(const CircuitBuilder& cb) {
    FastOutput out;
    int totalNodes = cb.L + (int)cb.nodes.size();
    out.putInt(totalNodes);
    out.putChar('\n');
    for (const auto& nd : cb.nodes) {
        out.putInt(nd.x);
        out.putChar(' ');
        out.putInt(nd.y);
        out.putChar(' ');
        out.putStr(FSTR[nd.f]);
        out.putChar('\n');
    }
    out.flush();
    cout.flush();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n);
    adj.reserve(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Build & print Alice machine
    {
        CircuitBuilder cb(n, k, 1500000);
        cb.buildMachine(adj, true);
        printMachine(cb);
    }

    // Build & print Bob machine
    {
        CircuitBuilder cb(n, k, 1500000);
        cb.buildMachine(adj, false);
        printMachine(cb);
    }

    return 0;
}

</syntaxhighlight>