Submission #960057

#TimeUsernameProblemLanguageResultExecution timeMemory
960057kilkuwuAlice, Bob, and Circuit (APIO23_abc)C++17
Compilation error
0 ms0 KiB
#include "abc.h" #include <bits/stdc++.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 // Alice int // returns la alice( /* in */ const int n, /* in */ const char names[][5], /* in */ const unsigned short numbers[], /* out */ bool outputs_alice[] ) { std::vector<int> ord(n); std::iota(ord.begin(), ord.end(), 0); std::sort(ord.begin(), ord.end(), [&](int i, int j) { return std::string(names[i]) < std::string(names[j]); }); int p = 0; auto add = [&](int x) { outputs_alice[p++] = x; }; for (int i = 0; i < n; i++) { int x = numbers[ord[i]]; for (int j = 0; j < 16; j++) { add(x >> j & 1); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { add(i == ord[j]); } } return p; } // Bob int // returns lb bob( /* in */ const int m, /* in */ const char senders[][5], /* in */ const char recipients[][5], /* out */ bool outputs_bob[] ) { std::vector<std::string> names(2 * m); for (int i = 0; i < m; i++) { names[2 * i] = senders[i]; names[2 * i + 1] = recipients[i]; } std::sort(names.begin(), names.end()); names.erase(std::unique(names.begin(), names.end()), names.end()); int n = names.size(); auto id = [&](std::string name) -> int { return std::lower_bound(names.begin(), names.end(), name) - names.begin(); }; std::vector<std::vector<int>> received(n, std::vector<int>(n)); for (int i = 0; i < m; i++) { int u = id(senders[i]); int v = id(recipients[i]); received[v][u] = 1; } int p = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { outputs_bob[p++] = received[i][j]; } } return p; } // 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] ) { using Num16 = std::array<int, 16>; int comp_gate = la + lb; auto add_op = [&](int op, int a, int b) -> int { operations[comp_gate] = op; operands[comp_gate][0] = a; operands[comp_gate][1] = b; comp_gate++; return comp_gate - 1; }; int zero = add_op(OP_XOR, 0, 0); Num16 zero16; for (int i = 0; i < 16; i++) zero16[i] = zero; auto bit_shift_left = [&](Num16 a, int amount) -> Num16 { if (amount >= 16) { return zero16; } for (int i = 15 - amount; i >= 0; i--) { a[i + amount] = a[i]; a[i] = zero; } return a; }; auto add_16 = [&](Num16 a, Num16 b) { int carry = zero; Num16 res; for (int i = 0; i < 16; i++) { int x = add_op(OP_XOR, a[i], b[i]); res[i] = add_op(OP_XOR, x, carry); carry = add_op(OP_OR, add_op(OP_AND, a[i], b[i]), add_op(OP_AND, x, carry)); } return res; }; auto and_16 = [&](Num16 a, int v) { Num16 res; for (int i = 0; i < 16; i++) { res[i] = add_op(OP_AND, a[i], v); } return res; }; auto multiply = [&](Num16 a, Num16 b) { Num16 res = zero16; for (int bit = 0; bit < 16; bit++) { res = add_16(res, and_16(a, b[bit])); a = bit_shift_left(a, 1); } // 0111 1011 // 0000000 return res; }; int n = std::sqrt(lb); auto get_received = [&](int i, int j) { return i * n + j + la; }; auto get_ord(int i, int j) { return i * n + j + n * 16; }; std::vector<Num16> numbers(n); for (int i = 0; i < n; i++) { for (int j = 0; j < 16; j++) { numbers[i][j] = i * 16 + j; } } std::vector<Num16> res(n, zero16); std::vector<Num16> real_res(n, zero16); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { res[i] = add_16(res[i], and_16(numbers[j], get_received(i, j))); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { real_res[i] = add_16(real_res[i], and_16(res[j], get_ord(i, j))); } } for (int i = 0; i < n; i++) { for (int j = 0; j < 16; j++) { outputs_circuit[i][j] = real_res[i][j]; } } return comp_gate; }

Compilation message (stderr)

abc.cpp: In function 'int circuit(int, int, int*, int (*)[2], int (*)[16])':
abc.cpp:179:30: error: a function-definition is not allowed here before '{' token
  179 |   auto get_ord(int i, int j) {
      |                              ^
abc.cpp:200:56: error: 'get_ord' was not declared in this scope
  200 |       real_res[i] = add_16(real_res[i], and_16(res[j], get_ord(i, j)));
      |                                                        ^~~~~~~