Submission #749718

#	Time	Username	Problem	Language	Result	Execution time	Memory
749718		Qwerty1232	Alice, Bob, and Circuit (APIO23_abc)	C++17	66 / 100	592 ms	493644 KiB

abc

#include <bits/stdc++.h>

#include "abc.h"

// you may find the definitions useful
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

constexpr int K = 16;
constexpr int S = 26;
constexpr int G = 20;

// Alice
int  // returns la
alice(/* in */ const int n, /* in */ const char names[][5], /* in */ const unsigned short numbers[], /* out */ bool outputs_alice[]) {
    // assert(n == 1);
    for (int t = 0; t < n; t++) {
        for (int i = 0; i < K; i++) {
            outputs_alice[t * (K + G) + i] = (numbers[t] >> i) & 1;
        }
        for (int i = 0; i < G; i++) {
            outputs_alice[t * (K + G) + K + i] = ((names[t][i / 5] - 'a') >> i % 5) & 1;
        }
    }
    return n * (K + G);
}

// Bob
int  // returns lb
bob(/*  in */ const int m, /*  in */ const char senders[][5], /*  in */ const char recipients[][5], /* out */ bool outputs_bob[]) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < G; j++) {
            outputs_bob[i * 2 * G + j] = ((senders[i][j / 5] - 'a') >> j % 5) & 1;
        }
        for (int j = 0; j < G; j++) {
            outputs_bob[i * 2 * G + G + j] = ((recipients[i][j / 5] - 'a') >> j % 5) & 1;
        }
    }
    return 2 * m * G;
}

// Circuit
int  // returns l
circuit(/*  in */ const int la, /*  in */ const int lb, /* out */ int operations[], /* out */ int operands[][2], /* out */ int outputs_circuit[][16]) {
    int len = la + lb;
    int n = la / (K + G);
    int m = lb / (2 * G);
    if (n == 0) {
        return len;
    }

    // assert(lb == S * S);

    auto add_op = [&](int op_code, int a, int b) {
        assert(len < int(2e7));
        operations[len] = op_code;
        operands[len][0] = a;
        operands[len][1] = b;
        len++;
        return len - 1;
    };

    auto make_cum = [&](std::vector<int> a, std::vector<int> b) -> std::vector<int> {
        assert(a.size() == K);
        assert(b.size() == K);

        std::vector<int> res;
        int carry = -1;
        for (int i = 0; i < K; i++) {
            if (carry == -1) {
                res.push_back(add_op(OP_XOR, a[i], b[i]));
                carry = add_op(OP_AND, a[i], b[i]);
            } else {
                int xx = add_op(OP_XOR, a[i], b[i]);
                res.push_back(add_op(OP_XOR, xx, carry));

                int ab = add_op(OP_AND, a[i], b[i]);
                int ac = add_op(OP_AND, a[i], carry);
                int bc = add_op(OP_AND, b[i], carry);

                carry = add_op(OP_OR, bc, add_op(OP_OR, ab, ac));
            }
        }
        return res;
    };

    std::vector<std::vector<int>> init(n, std::vector<int>(K));
    std::vector<std::vector<int>> names(n, std::vector<int>(G));
    for (int i = 0; i < n; i++) {
        std::iota(init[i].begin(), init[i].end(), i * (K + G));
        std::iota(names[i].begin(), names[i].end(), i * (K + G) + K);
    }

    std::vector<std::vector<int>> shit(m, std::vector<int>(2 * G));
    for (int i = 0; i < m; i++) {
        std::iota(shit[i].begin(), shit[i].end(), la + i * 2 * G);
    }

    std::vector<std::vector<int>> val(n, std::vector<int>(K, add_op(OP_ZERO, 0, 0)));

    const int zero = add_op(OP_ZERO, 0, 0);
    const int one = add_op(OP_ONE, 0, 0);

    auto copy_if = [&](int b, std::vector<int> val) {
        std::vector<int> copy(K);
        for (int i = 0; i < K; i++) {
            copy[i] = add_op(OP_AND, val[i], b);
        }
        return copy;
    };
    // auto _if = [&](int b, std::vector<int> val) {
    //     std::vector<int> copy(K);
    //     for (int i = 0; i < K; i++) {
    //         copy[i] = add_op(OP_AND, val[i], b);
    //     }
    //     return copy;
    // };
    for (int t = 0; t < m; t++) {
        std::vector<int> fuck(K, zero);

        for (int i = 0; i < n; i++) {
            int eq = one;
            for (int j = 0; j < G; j++) {
                eq = add_op(OP_AND, eq, add_op(OP_EQUAL, names[i][j], shit[t][j]));
            }
            fuck = make_cum(fuck, copy_if(eq, init[i]));
        }
        for (int i = 0; i < n; i++) {
            int eq = one;
            for (int j = 0; j < G; j++) {
                eq = add_op(OP_AND, eq, add_op(OP_EQUAL, names[i][j], shit[t][G + j]));
            }
            val[i] = make_cum(val[i], copy_if(eq, fuck));
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < K; j++) {
            outputs_circuit[i][j] = val[i][j];
        }
    }

    return len;
}

• 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: 0 / 18
• Subtask 8: 0 / 10
• Subtask 9: 0 / 6