Submission #1192282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192282		ainunnajib	Alice, Bob, and Circuit (APIO23_abc)	C++20	36 / 100	272 ms	195976 KiB

abc

#include <vector>
#include <string>
#include <map>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>

// --- Global variables for circuit construction ---
int next_gate_idx;
std::vector<int>* circuit_operations;
std::vector<std::vector<int>>* circuit_operands;

// --- Helper function to create a new gate ---
int create_gate(int op_type, int in1, int in2) {
    if (next_gate_idx >= circuit_operations->size()) {
        // Resize if needed, although the problem implies pre-allocation
        // based on the return value of circuit(). For safety, let's resize.
        // Note: Resizing might be slow; ideally, predict the size.
        // The maximum is 2e7 gates. Let's assume vectors grow as needed.
         circuit_operations->resize(next_gate_idx + 1000); // Grow in chunks
         circuit_operands->resize(next_gate_idx + 1000);
    }
    (*circuit_operations)[next_gate_idx] = op_type;
    (*circuit_operands)[next_gate_idx] = {in1, in2};
    return next_gate_idx++;
}

// --- Basic Logic Gates ---
// Reference table from PDF [cite: 25]
// NOT x0: p=5 (inputs x0, x0) -> f(5, x0, x0) = NOT x0
// x0 AND x1: p=8 -> f(8, x0, x1)
// x0 OR x1: p=14 -> f(14, x0, x1)
// x0 XOR x1: p=6 -> f(6, x0, x1)
// CONST 0: p=0 -> f(0, x0, x1) = 0 (use dummy inputs, e.g., gate 0, 0)
// CONST 1: p=15 -> f(15, x0, x1) = 1 (use dummy inputs, e.g., gate 0, 0)

int gate_const_0 = -1;
int gate_const_1 = -1;

void initialize_constants() {
    // Create constant gates if not already done
    // Need dummy inputs. Use gate 0 if la+lb > 0, otherwise handle gracefully.
    // Let's assume la+lb >= 1, so gate 0 exists.
    int dummy_input = 0; // Assuming at least one input gate exists
     if (gate_const_0 == -1) {
        gate_const_0 = create_gate(0, dummy_input, dummy_input);
     }
    if (gate_const_1 == -1) {
         gate_const_1 = create_gate(15, dummy_input, dummy_input);
    }
}


int create_not(int in) {
    return create_gate(5, in, in); // NOT x0 = f(5, x0, x0)
}

int create_and(int in1, int in2) {
    return create_gate(8, in1, in2); // AND = f(8, x0, x1)
}

int create_or(int in1, int in2) {
    return create_gate(14, in1, in2); // OR = f(14, x0, x1)
}

int create_xor(int in1, int in2) {
    return create_gate(6, in1, in2); // XOR = f(6, x0, x1)
}


// --- 1-bit Full Adder ---
// inputs: a, b, carry_in
// outputs: sum_out, carry_out
struct FullAdderResult {
    int sum_gate;
    int carry_gate;
};

FullAdderResult create_full_adder(int a_gate, int b_gate, int carry_in_gate) {
    int xor1 = create_xor(a_gate, b_gate);
    int sum_out = create_xor(xor1, carry_in_gate);

    int and1 = create_and(a_gate, b_gate);
    int and2 = create_and(xor1, carry_in_gate);
    int carry_out = create_or(and1, and2);

    return {sum_out, carry_out};
}

// --- 16-bit Ripple Carry Adder ---
// inputs: a[16], b[16], carry_in
// outputs: sum[16], carry_out
struct Adder16BitResult {
    std::vector<int> sum_gates; // 16 gates
    int carry_out_gate;
};

Adder16BitResult create_16bit_adder(const std::vector<int>& a_gates, const std::vector<int>& b_gates, int carry_in_gate) {
    std::vector<int> sum_gates(16);
    int current_carry = carry_in_gate;

    for (int i = 0; i < 16; ++i) {
        FullAdderResult fa_res = create_full_adder(a_gates[i], b_gates[i], current_carry);
        sum_gates[i] = fa_res.sum_gate;
        current_carry = fa_res.carry_gate;
    }

    return {sum_gates, current_carry};
}

// --- Multiplexer (16-bit 2-to-1) ---
// sel=0 -> out=in0, sel=1 -> out=in1
// out = (in0 AND (NOT sel)) OR (in1 AND sel)
std::vector<int> create_16bit_mux(int sel_gate, const std::vector<int>& in0_gates, const std::vector<int>& in1_gates) {
    std::vector<int> out_gates(16);
    int not_sel = create_not(sel_gate);
    for (int i = 0; i < 16; ++i) {
        int term0 = create_and(in0_gates[i], not_sel);
        int term1 = create_and(in1_gates[i], sel_gate);
        out_gates[i] = create_or(term0, term1);
    }
    return out_gates;
}

// --- Comparator (k-bit equality check) ---
// returns 1 if a == b, 0 otherwise
int create_k_bit_comparator(const std::vector<int>& a_gates, const std::vector<int>& b_gates) {
    int k = a_gates.size();
    if (k == 0) return gate_const_1; // Empty vectors are equal

    std::vector<int> xnor_gates(k);
    for (int i = 0; i < k; ++i) {
        int xor_gate = create_xor(a_gates[i], b_gates[i]);
        xnor_gates[i] = create_not(xor_gate); // XNOR = NOT(XOR)
    }

    // AND all XNOR results
    int result_gate = xnor_gates[0];
    for (int i = 1; i < k; ++i) {
        result_gate = create_and(result_gate, xnor_gates[i]);
    }
    return result_gate;
}


// --- N-to-1 16-bit Multiplexer (using tree of 2-to-1 MUXes) ---
// selects one of N=inputs.size() 16-bit inputs based on select_bits
// select_bits has k = ceil(log2(N)) bits
std::vector<int> create_n_to_1_mux_16bit(const std::vector<int>& select_bits, const std::vector<std::vector<int>>& inputs) {
    int n = inputs.size();
    if (n == 0) return std::vector<int>(16, gate_const_0); // Or handle error
    if (n == 1) return inputs[0];

    std::vector<std::vector<int>> current_level_inputs = inputs;
    int current_select_bit_idx = 0;

    while (current_level_inputs.size() > 1) {
        std::vector<std::vector<int>> next_level_inputs;
        int current_size = current_level_inputs.size();
        int selector_gate = select_bits[current_select_bit_idx];

        for (int i = 0; i < current_size; i += 2) {
            if (i + 1 < current_size) {
                next_level_inputs.push_back(create_16bit_mux(selector_gate, current_level_inputs[i], current_level_inputs[i+1]));
            } else {
                // Odd number of inputs, pass the last one through, potentially gated by the selector?
                // A standard mux tree handles powers of 2. For non-powers-of-2, padding or careful handling is needed.
                // Let's assume N is padded to a power of 2 or handled appropriately.
                // Simplest: pass through if it's the last one.
                 next_level_inputs.push_back(current_level_inputs[i]);
                 // Proper handling might involve muxing with a zero vector if the selector is 1 for this last element.
                 // For now, assume the structure aligns or padding handles this.
            }
        }
        current_level_inputs = next_level_inputs;
        current_select_bit_idx++;
    }
    return current_level_inputs[0];
}

// --- Alice ---
// Encodes member numbers into a binary string.
// Assumes names map to indices 0 to n-1 based on input order.
// Output: outputs_alice = [num0_bit0, ..., num0_bit15, num1_bit0, ..., num1_bit15, ...]
// Return value: l_A = 16 * n
int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]) {
    if (n == 0) return 0;
    int l_A = 16 * n;
    for (int i = 0; i < n; ++i) {
        unsigned short num = numbers[i];
        for (int j = 0; j < 16; ++j) {
            outputs_alice[i * 16 + j] = (num >> j) & 1;
        }
    }
    return l_A;
}

// --- Bob ---
// Encodes the m letters (sender, recipient) into a binary string.
// CRITICAL ASSUMPTION: Bob can map names to indices 0..n-1 consistently with Alice.
// This usually requires Bob knowing n and the ordered list of names.
// Since they aren't passed, we assume implicit context or a standard ordering (e.g., lexicographical if specified).
// Let's simulate this by building the map here. In a real contest, this mapping needs clarification.
// Output: outputs_bob = [sender1_idx_bits, recipient1_idx_bits, sender2_idx_bits, ...]
// Return value: l_B = m * 2 * k, where k = ceil(log2(n))
// Note: If n=0 or n=1, k=1 bit needed for index. Handle n=0 case. Handle k=0 if n=1.
int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]) {
    if (m == 0) return 0;

    // --- Determine n and create name-to-index map ---
    // This is the problematic part. We *assume* we can reconstruct the map.
    // Let's deduce n and the map from the unique names in senders/recipients.
    // Sort them to get a consistent order IF that's the implicit rule.
    // THIS IS A GUESS based on typical contest scenarios.
    std::map<std::string, int> name_to_index;
    std::vector<std::string> unique_names;
    std::map<std::string, bool> seen_names;

    for (int i = 0; i < m; ++i) {
        if (seen_names.find(senders[i]) == seen_names.end()) {
            unique_names.push_back(senders[i]);
            seen_names[senders[i]] = true;
        }
        if (seen_names.find(recipients[i]) == seen_names.end()) {
            unique_names.push_back(recipients[i]);
            seen_names[recipients[i]] = true;
        }
    }
    // If subtasks guarantee a specific order (e.g., a-z, aa-zz), use that.
    // Otherwise, sorting alphabetically is a common default.
    std::sort(unique_names.begin(), unique_names.end());

    // If the problem guarantees all n members appear
    // or implies a fixed order (like subtasks 4, 7), use that info.
    // Without explicit info, deducing 'n' reliably is hard if some members don't interact.
    // Let's assume unique_names gives us the relevant members in *some* order.
    // The true 'n' might be larger. This needs problem clarification.
    // For now, proceed with the deduced list.
    int deduced_n = unique_names.size();
    for (int i = 0; i < deduced_n; ++i) {
        name_to_index[unique_names[i]] = i;
    }
    // If the actual 'n' from Alice is needed, we have a problem.
    // Let's assume deduced_n is the effective 'n' for indexing.

    if (deduced_n == 0) return 0; // No members involved in letters.

    int k = (deduced_n <= 1) ? 1 : std::ceil(std::log2(deduced_n)); // Bits per index
    int l_B = m * 2 * k;
    int current_bit = 0;

    for (int i = 0; i < m; ++i) {
        int sender_idx = name_to_index[senders[i]];
        int recipient_idx = name_to_index[recipients[i]];

        // Write sender index (k bits)
        for (int bit_idx = 0; bit_idx < k; ++bit_idx) {
            outputs_bob[current_bit++] = (sender_idx >> bit_idx) & 1;
        }
        // Write recipient index (k bits)
        for (int bit_idx = 0; bit_idx < k; ++bit_idx) {
            outputs_bob[current_bit++] = (recipient_idx >> bit_idx) & 1;
        }
    }

    return l_B;
}


// --- Circuit ---
// Builds the circuit to calculate the sums.
int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]) {
    if (la == 0) return la + lb; // No members, circuit is just inputs.

    // --- Setup ---
    next_gate_idx = la + lb;
    // Assign pointers to the output arrays
    // NOTE: Directly modifying input arrays like this is unusual.
    // Ensure this matches the expected behavior of the grader interface.
    std::vector<int> ops_vec(next_gate_idx); // Start with space for input gates
    std::vector<std::vector<int>> opnds_vec(next_gate_idx, std::vector<int>(2, -1));
    circuit_operations = &ops_vec;
    circuit_operands = &opnds_vec;


    initialize_constants(); // Create CONST 0 and 1 gates

    int n = la / 16;
    int k = (n <= 1) ? 1 : std::ceil(std::log2(n)); // Bits per index
    int m = (k == 0 || lb == 0) ? 0 : lb / (2 * k); // Deduce m


    // --- Prepare Constant Index Representations ---
    std::vector<std::vector<int>> constant_indices(n, std::vector<int>(k));
    for(int j=0; j<n; ++j) {
        for(int bit=0; bit<k; ++bit) {
            constant_indices[j][bit] = ((j >> bit) & 1) ? gate_const_1 : gate_const_0;
        }
    }

    // --- Prepare Constant 16-bit Zero ---
     std::vector<int> zero_16bit(16, gate_const_0);


    // --- Process Messages and Accumulate Sums ---
    std::vector<std::vector<int>> recipient_sums(n, zero_16bit); // Initialize sums to 0

    // Iterate through each message encoded by Bob
    for (int msg_idx = 0; msg_idx < m; ++msg_idx) {
        // --- Decode Sender and Recipient Indices for this message ---
        std::vector<int> sender_idx_gates(k);
        std::vector<int> recipient_idx_gates(k);
        int base_bob_idx = la + msg_idx * 2 * k;
        for (int bit = 0; bit < k; ++bit) {
            sender_idx_gates[bit] = base_bob_idx + bit;
            recipient_idx_gates[bit] = base_bob_idx + k + bit;
        }

        // --- Select Sender's Number using N-to-1 MUX ---
        // Prepare inputs for the MUX: pointers to Alice's input gates for each member
        std::vector<std::vector<int>> sender_number_inputs(n, std::vector<int>(16));
         for(int sender_id=0; sender_id < n; ++sender_id) {
             for(int bit=0; bit < 16; ++bit) {
                 sender_number_inputs[sender_id][bit] = sender_id * 16 + bit;
             }
         }
         // This MUX is potentially huge and slow to build.
         // Optimization: Instead of a full MUX, directly compute the gated value for each adder.

        // --- Alternative: Compute Gated Number per Recipient ---
        // For each recipient j, calculate: N_sender_if_recipient_matches = (N_sender if R == j else 0)

         std::vector<int> selected_sender_number; // Placeholder

         // We need N_sender based on sender_idx_gates. This still requires a MUX.
         // Let's assume create_n_to_1_mux_16bit works, although it might be too slow/large.
         if (n > 0) {
             selected_sender_number = create_n_to_1_mux_16bit(sender_idx_gates, sender_number_inputs);
         } else {
             selected_sender_number = zero_16bit; // Handle n=0 case
         }


        // --- Add Selected Sender Number to the Correct Recipient's Sum ---
        for (int j = 0; j < n; ++j) {
             // Create comparator: is_recipient = (recipient_idx == j) ?
            int is_recipient_gate = create_k_bit_comparator(recipient_idx_gates, constant_indices[j]);

             // Gate the sender's number: gated_number = selected_sender_number AND is_recipient
             std::vector<int> gated_number(16);
             for (int bit = 0; bit < 16; ++bit) {
                 gated_number[bit] = create_and(selected_sender_number[bit], is_recipient_gate);
             }

            // Add the gated number to the current sum for recipient j
             Adder16BitResult add_res = create_16bit_adder(recipient_sums[j], gated_number, gate_const_0); // carry_in = 0
             recipient_sums[j] = add_res.sum_gates; // Update sum for next message
             // We ignore the final carry_out as it's modulo 2^16
         }
     }

     // --- Final Output Assignment ---
     for (int j = 0; j < n; ++j) {
         for (int bit = 0; bit < 16; ++bit) {
             outputs_circuit[j][bit] = recipient_sums[j][bit];
         }
     }

    // --- Copy local vectors to output arrays ---
    // Ensure the output arrays are large enough.
    // The grader expects modifications in place, but our helper functions used vectors.
    // Resize output arrays if necessary (risky if fixed size expected).
    // Copy contents.
    int final_gate_count = next_gate_idx;
    if (final_gate_count > 20000000) {
        // Handle error: Too many gates
        // Perhaps print to cerr or return a specific error code if possible
        // For now, just proceed, but the solution might be marked wrong.
    }

    // Directly copy results into the provided arrays.
    // Assume operations and operands have sufficient size allocated by the grader based on return value.
    for(int i=la+lb; i<final_gate_count; ++i) {
        if (i < ops_vec.size()) { // Basic bounds check
           operations[i] = ops_vec[i];
           operands[i][0] = opnds_vec[i][0];
           operands[i][1] = opnds_vec[i][1];
        } else {
            // This shouldn't happen if vector growth worked correctly
            // Handle error or break
            break;
        }
    }


    return final_gate_count;
}

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