Submission #960030

#TimeUsernameProblemLanguageResultExecution timeMemory
960030kilkuwuAlice, Bob, and Circuit (APIO23_abc)C++17
0 / 100
118 ms10252 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[] ) { for (int i = 0; i < 16; i++) { outputs_alice[i] = numbers[0] >> i & 1; } return 16; } // 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 < 16; i++) { outputs_bob[i] = m >> i & 1; } return 16; } // 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 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; }; // basically bit shifting // xor same equal 0 int zero = add_op(OP_XOR, 0, 0); using Num16 = std::array<int, 16>; 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++) { a = bit_shift_left(a, 1); res = add_16(res, and_16(a, b[bit])); } return res; }; Num16 n, m; for (int i = 0; i < 16; i++) { n[i] = i; } for (int i = 0; i < 16; i++) { m[i] = i; } auto res = multiply(n, m); for (int i = 0; i < 16; i++) { outputs_circuit[0][i] = res[i]; } return comp_gate; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...