oj.uz

Submission #749718

# Submission time Handle Problem Language Result Execution time Memory
749718 2023-05-28T12:07:33 Z Qwerty1232 Alice, Bob, and Circuit (APIO23_abc) C++17
66 / 100
 592 ms 493644 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Correct!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Correct!
2 Correct 3 ms 1220 KB Correct!

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Correct!
2 Correct 3 ms 1220 KB Correct!
3 Correct 146 ms 23472 KB Correct!
4 Correct 155 ms 23512 KB Correct!

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3988 KB Correct!
2 Correct 192 ms 96072 KB Correct!
3 Correct 240 ms 124584 KB Correct!

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3988 KB Correct!
2 Correct 192 ms 96072 KB Correct!
3 Correct 240 ms 124584 KB Correct!
4 Correct 194 ms 96480 KB Correct!
5 Correct 250 ms 124424 KB Correct!

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3988 KB Correct!
2 Correct 192 ms 96072 KB Correct!
3 Correct 240 ms 124584 KB Correct!
4 Correct 194 ms 96480 KB Correct!
5 Correct 250 ms 124424 KB Correct!
6 Correct 180 ms 90676 KB Correct!
7 Correct 355 ms 188456 KB Correct!

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 592 ms 493644 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 592 ms 493644 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Correct!
2 Correct 3 ms 1220 KB Correct!
3 Correct 146 ms 23472 KB Correct!
4 Correct 155 ms 23512 KB Correct!
5 Correct 11 ms 3988 KB Correct!
6 Correct 192 ms 96072 KB Correct!
7 Correct 240 ms 124584 KB Correct!
8 Correct 194 ms 96480 KB Correct!
9 Correct 250 ms 124424 KB Correct!
10 Correct 180 ms 90676 KB Correct!
11 Correct 355 ms 188456 KB Correct!
12 Runtime error 592 ms 493644 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -