#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
// Aliases
const int BIT_LENGTH = 16;
using u16 = unsigned short;
namespace {
struct GateOutput {
int operation;
int op0, op1;
GateOutput(int _op, int _op0, int _op1):
operation(_op), op0(_op0), op1(_op1) {}
};
int gate_index;
std::vector<GateOutput> outputs;
}
struct LogicGate {
int idx;
int operation;
const LogicGate *op0, *op1;
LogicGate() {}
LogicGate(int _op, const LogicGate *_op0, const LogicGate *_op1) :
idx(gate_index++), operation(_op), op0(_op0), op1(_op1) {
outputs.emplace_back(operation, op0->idx, op1->idx);
}
};
namespace {
std::vector<LogicGate*> input_gates;
LogicGate *zerobit, *onebit;
}
struct Number {
std::array<LogicGate*, BIT_LENGTH> digits;
Number() {}
Number(std::vector<LogicGate*> _digits){
for (int i = 0; i < BIT_LENGTH; i++) digits[i] = _digits[i];
}
// Cost: 80 operations
// Can be optimized to be 74 operations
Number operator + (const Number &B) {
const Number A = *this;
Number result;
LogicGate* carry = zerobit;
for (int i = 0; i < BIT_LENGTH; i++){
LogicGate D(OP_XOR, A.digits[i], B.digits[i]);
LogicGate CR(OP_AND, A.digits[i], B.digits[i]);
LogicGate new_digit(OP_XOR, &D, carry);
LogicGate carry2(OP_AND, carry, &D);
LogicGate new_carry(OP_OR, &CR, &carry2);
result.digits[i] = &new_digit;
carry = &new_carry;
}
return result;
}
// Cost: 16 operations
Number operator & (const LogicGate *gate){
const Number A = *this;
Number result;
for (int i = 0; i < BIT_LENGTH; i++){
LogicGate new_digit(OP_AND, A.digits[i], gate);
result.digits[i] = &new_digit;
}
return result;
}
// Cost: 0 operation
Number operator << (int shift) {
const Number A = *this;
Number result;
for (int i = 0; i < 16; i++){
int j = i - shift;
if (j < 0) result.digits[i] = zerobit;
else result.digits[i] = A.digits[j];
}
return result;
}
// Bad multiplication
Number operator * (const Number &B) {
const Number A = *this;
Number result(std::vector<LogicGate*>(BIT_LENGTH, zerobit));
Number current = A;
for (int i = 0; i < BIT_LENGTH; i++){
result = result + (current & B.digits[i]);
current = current << 1;
}
return result;
}
};
// Cost: 2 operations
void initialize(const int la, const int lb){
gate_index = la + lb;
input_gates.resize(la + lb);
*zerobit = LogicGate(OP_ZERO, input_gates[0], input_gates[1]);
*onebit = LogicGate(OP_ONE, input_gates[0], input_gates[1]);
}
// Alice
int alice(
const int n,
const char names[][5],
const u16 numbers[],
bool outputs_alice[]
) {
// For subtask A, we only need to send the number, since n = 1
for (int i = 0; i < 16; i++)
outputs_alice[i] = ((numbers[0] >> i) & 1);
return 16;
}
// Bob
int bob(
const int m,
const char senders[][5],
const char recipients[][5],
bool outputs_bob[]
) {
// For subtask A, we only need to send m, since n = 1
for (int i = 0; i < 16; i++)
outputs_bob[i] = ((m >> i) & 1);
return 16;
}
// Circuit
int circuit(
const int la,
const int lb,
int operations[],
int operands[][2],
int outputs_circuit[][16]
) {
initialize(la, lb);
std::vector<LogicGate*> digits_A(la), digits_B(lb);
for (int i = 0; i < la; i++){
digits_A[i] = input_gates[i];
}
for (int i = 0; i < lb; i++){
digits_B[i] = input_gates[i + la];
}
Number numA(digits_A), numB(digits_B);
Number res = numA * numB;
// Output
int crr = la + lb;
for (auto gate_output: outputs){
operations[crr] = gate_output.operation;
operands[crr][0] = gate_output.op0;
operands[crr][1] = gate_output.op1;
crr++;
}
for (int i = 0; i < 16; i++){
outputs_circuit[0][i] = res.digits[i]->idx;
}
return crr;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
1348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
1348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
