#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
// 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
const int BITS = 16;
// 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 < n; i++) {
for (int j = 0; j < BITS; j++) {
outputs_alice[i * BITS + j] = ((numbers[i] >> j) & 1);
}
}
return n * BITS;
}
// Bob
int // returns lb
bob(
/* in */ const int m,
/* in */ const char senders[][5],
/* in */ const char recipients[][5],
/* out */ bool outputs_bob[]
) {
int n = 26;
vector<vector<bool>> rec(n, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
rec[recipients[i][0] - 'a'][senders[i][0] - 'a'] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
outputs_bob[i * n + j] = rec[i][j];
}
}
return n*n;
}
// Circuit
int gate;
vector<int> make_0(int operations[], int operands[][2]) {
vector<int> fin;
for (int i = 0; i < BITS; i++) {
operands[gate][0] = 0;
operands[gate][1] = 1;
operations[gate] = OP_ZERO;
fin.push_back(gate);
gate++;
}
return fin;
}
vector<int> get_and(vector<int> rr, int bitIdx, int operations[], int operands[][2]) {
vector<int> fin;
for (int i = 0; i < BITS; i++) {
operands[gate][0] = rr[i];
operands[gate][1] = bitIdx;
operations[gate] = OP_AND;
fin.push_back(gate);
gate++;
}
return fin;
}
// carry : (carry && (a || b)) || ((!carry) && (a && b))
vector<int> addition(vector<int> a, vector<int> b, int operations[], int operands[][2]) {
vector<int> carryPos;
// creates carry array
for (int i = 0; i < BITS; i++) {
if (carryPos.empty()) {
// iff a && b
operands[gate][0] = a[i];
operands[gate][1] = b[i];
operations[gate] = OP_AND;
carryPos.push_back(gate);
gate++;
continue;
}
// builds (carry && (a || b))
operands[gate][0] = a[i];
operands[gate][1] = b[i];
operations[gate] = OP_OR;
operands[gate+1][0] = gate;
operands[gate+1][1] = carryPos.back();
operations[gate+1] = OP_AND;
// builds (!carry) && (a && b)
operands[gate+2][0] = a[i];
operands[gate+2][1] = b[i];
operations[gate+2] = OP_AND;
operands[gate+3][0] = carryPos.back();
operands[gate+3][1] = 0;
operations[gate+3] = OP_NOT_X0;
operands[gate+4][0] = gate+2;
operands[gate+4][1] = gate+3;
operations[gate+4] = OP_AND;
// combines the two with ||
operands[gate+5][0] = gate+1;
operands[gate+5][1] = gate+4;
operations[gate+5] = OP_OR;
carryPos.push_back(gate+5);
gate += 6;
}
// adds the number
// the ith bit is on if and only if (carry && !(a ^ b)) || (!carry && (a ^ b))
vector<int> fin;
for (int i = 0; i < BITS; i++) {
if (i == 0) {
operands[gate][0] = a[i];
operands[gate][1] = b[i];
operations[gate] = OP_XOR;
fin.push_back(gate);
gate++;
continue;
}
int carry = carryPos[i-1];
// builds (carry && (a == b))
operands[gate][0] = a[i];
operands[gate][1] = b[i];
operations[gate] = OP_EQUAL;
operands[gate+1][0] = carry;
operands[gate+1][1] = gate;
operations[gate+1] = OP_AND;
// builds (!carry && (a ^ b))
operands[gate+2][0] = a[i];
operands[gate+2][1] = b[i];
operations[gate+2] = OP_XOR;
operands[gate+3][0] = carry;
operands[gate+3][1] = carry;
operations[gate+3] = OP_NOT_X0;
operands[gate+4][0] = gate+2;
operands[gate+4][1] = gate+3;
operations[gate+4] = OP_AND;
// merges them with ||
operands[gate+5][0] = gate+1;
operands[gate+5][1] = gate+4;
operations[gate+5] = OP_OR;
fin.push_back(gate+5);
gate += 6;
}
return fin;
}
int // returns l
circuit(
/* in */ const int la,
/* in */ const int lb,
/* out */ int operations[],
/* out */ int operands[][2],
/* out */ int outputs_circuit[][16]
) {
gate = la + lb;
int n = 26;
vector<vector<int>> vals(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < BITS; j++) {
vals[i].push_back(i * BITS + j);
}
}
for (int i = 0; i < n; i++) {
vector<int> res = make_0(operations, operands);
for (int j = 0; j < n; j++) {
vector<int> willAdd = get_and(vals[j], la + i * n + j, operations, operands);
res = addition(willAdd, res, operations, operands);
}
for (int j = 0; j < BITS; j++) {
outputs_circuit[i][j] = res[j];
}
}
return gate;
}
