#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
namespace string_encode
{
const int length_offset[5] = {0, 0, 26,
26 + 26 * 26,
26 + 26 * 26 + 26 * 26 * 26};
int ctoi(const char *a)
{
int ptr = 0, result = 0;
for (; a[ptr]; ptr++)
result = result * 26 + a[ptr] - 'a';
return result + length_offset[ptr];
}
}
// Alice
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs_alice[])
{
vector<int> name(n);
for (int i = 0; i < n; i++)
name[i] = string_encode::ctoi(names[i]);
vector<unsigned short> nums(n);
copy(numbers, numbers + n, nums.begin());
}
// Bob
int // returns lb
bob(
/* in */ const int m,
/* in */ const char senders[][5],
/* in */ const char recipients[][5],
/* out */ bool outputs_bob[])
{
vector<pair<int, int>> msg(m);
for (int i = 0; i < m; i++)
msg[i] = {string_encode::ctoi(senders[i]),
string_encode::ctoi(recipients[i])};
}
namespace bit_store
{
struct bit
{
int v = -1;
bool is_stpd() const
{
return v == -1;
}
};
bit zero, one;
enum OP
{
OP_ZERO, // f(OP_ZERO, x0, x1) = 0
OP_NOR, // f(OP_NOR, x0, x1) = !(x0 || x1)
OP_GREATER, // f(OP_GREATER, x0, x1) = (x0 > x1)
OP_NOT_X1, // f(OP_NOT_X1, x0, x1) = !x1
OP_LESS, // f(OP_LESS, x0, x1) = (x0 < x1)
OP_NOT_X0, // f(OP_NOT_X0, x0, x1) = !x0
OP_XOR, // f(OP_XOR, x0, x1) = (x0 ^ x1)
OP_NAND, // f(OP_NAND, x0, x1) = !(x0 && x1)
OP_AND, // f(OP_AND, x0, x1) = (x0 && x1)
OP_EQUAL, // f(OP_EQUAL, x0, x1) = (x0 == x1)
OP_X0, // f(OP_X0, x0, x1) = x0
OP_GEQ, // f(OP_GEQ, x0, x1) = (x0 >= x1)
OP_X1, // f(OP_X1, x0, x1) = x1
OP_LEQ, // f(OP_LEQ, x0, x1) = (x0 <= x1)
OP_OR, // f(OP_OR, x0, x1) = (x0 || x1)
OP_ONE, // f(OP_ONE, x0, x1) = 1
NOT_CONSTRUCTED // Input bits
};
// Construction of bit
struct bcstr
{
OP op;
bit x, y;
};
}
namespace num_store
{
struct num
{
static const int MAXSIZE = 19;
bit_store::bit bits[MAXSIZE];
num() {}
void init_input(const int SIZE);
void init_value(int v);
};
}
namespace bit_mani
{
using namespace bit_store;
struct io_bits
{
bit zero, one;
int input_size = 0, input_ptr = 0;
vector<bcstr> cstr;
bit make_bit(OP op, bit x, bit y)
{
assert(x.v != -1 && y.v != -1 && op != NOT_CONSTRUCTED);
cstr.push_back({op, x, y});
return bit{int(cstr.size() - 1)};
};
io_bits() {}
io_bits(int input_size) : input_size(input_size), cstr(input_size, {NOT_CONSTRUCTED})
{
zero = make_bit(OP_ZERO, bit{0}, bit{0});
one = make_bit(OP_ONE, bit{0}, bit{0});
}
void erase_deps(vector<num_store::num> &results)
{
vector<int> act(cstr.size());
for (int i = 0; i < input_size; i++)
act[i] = 1;
for (num_store::num &v : results)
{
for (bit &x : v.bits)
{
x = x.is_stpd() ? zero : x;
act[x.v] = 1;
}
}
for (int i = act.size() - 1; i >= input_size; i--)
{
if (act[i] == 0)
continue;
assert(cstr[i].x.v < i && cstr[i].y.v < i);
act[cstr[i].x.v] = act[cstr[i].y.v] = 1;
}
int cnt = 0;
vector<bcstr> s;
for (int i = 0; i < cstr.size(); i++)
{
if (act[i] == 0)
continue;
act[i] = cnt++;
s.push_back({cstr[i].op, bit{act[cstr[i].x.v]}, bit{act[cstr[i].y.v]}});
}
cstr = move(s);
for (num_store::num &v : results)
{
for (bit &x : v.bits)
x.v = act[x.v];
}
}
int write(int ops[], int opers[][2], int outputs[][16], vector<num_store::num> &results){
erase_deps(results);
for (int i = input_size; i < cstr.size(); i++)
{
ops[i] = cstr[i].op;
opers[i][0] = cstr[i].x.v;
opers[i][1] = cstr[i].y.v;
}
for (int i = 0; i < results.size(); i++)
for (int j = 0; j < 16; j++)
outputs[i][j] = results[i].bits[j].v;
return cstr.size();
}
} strm;
#define DEF_OP(op, name) \
bit operator op(const bit &a, const bit &b) { return strm.make_bit(name, a, b); }
DEF_OP(^, OP_XOR)
DEF_OP(&, OP_AND)
DEF_OP(|, OP_OR)
DEF_OP(==, OP_EQUAL)
#undef DEF_OP
}
namespace num_store{
using bit_mani::strm;
void num_store::num::init_input(const int SIZE)
{
for (int i = 0; i < SIZE; i++)
bits[i].v = strm.input_ptr++;
for (int i = SIZE; i < MAXSIZE; i++)
bits[i] = strm.zero;
}
void num_store::num::init_value(int v)
{
for (int i = 0; i < MAXSIZE; i++)
bits[i] = (v & (1 << i)) ? strm.one : strm.zero;
}
}
namespace num_mani
{
using num_store::num;
using namespace bit_mani;
using bit_mani::operator&, bit_mani::operator^, bit_mani::operator|, bit_mani::operator==;
num operator+(const num &l, const num &r)
{
num result;
int ptr = 0;
for (; ptr < 16 && (l.bits[ptr].is_stpd() && r.bits[ptr].is_stpd()); ptr++)
result.bits[ptr].v = -1;
for (; ptr < 16 && (l.bits[ptr].is_stpd() || r.bits[ptr].is_stpd()); ptr++)
result.bits[ptr] = (l.bits[ptr].v != -1 ? l.bits[ptr] : r.bits[ptr]);
for (bit three{-1}; ptr < 16; ptr++)
{
bit one = l.bits[ptr], two = r.bits[ptr];
assert(one.v != -1 && two.v != -1);
if (three.is_stpd())
{
result.bits[ptr] = one ^ two;
three = one & two;
}
else
{
bit four = one ^ two;
bit five = result.bits[ptr] = four ^ three;
bit six = one & two;
bit seven = four & three;
three = six | seven;
}
}
return result;
}
num operator<<(const num &a, int b)
{
num result;
copy(a.bits, a.bits + 16 - b, result.bits + b);
return result;
}
num operator&(const num &a, const bit &g)
{
num result;
for (int i = 0; i < 16; i++)
{
if (a.bits[i].is_stpd())
continue;
result.bits[i] = a.bits[i] & g;
}
return result;
}
num operator*(const num &lhs, const num &rhs)
{
int sizeab = strm.cstr.size();
num ab;
{
num nb = rhs;
for (int i = 0; i < 16; i++)
{
if (lhs.bits[i].is_stpd())
continue;
num anb = nb & lhs.bits[i];
ab = ab + anb;
nb = nb << 1;
}
sizeab = strm.cstr.size() - sizeab;
}
int sizeba = strm.cstr.size();
num ba;
{
num na = lhs;
for (int i = 0; i < 16; i++)
{
if (rhs.bits[i].is_stpd())
continue;
num ana = na & rhs.bits[i];
ba = ba + ana;
na = na << 1;
}
sizeba = strm.cstr.size() - sizeab;
}
if (sizeab <= sizeba)
return ab;
else
return ba;
}
num operator|(const num &lhs, const num &rhs)
{
num result;
for (int i = 0; i < 16; i++)
{
if (lhs.bits[i].is_stpd())
result.bits[i] = rhs.bits[i];
else if (rhs.bits[i].is_stpd())
result.bits[i] = lhs.bits[i];
else
result.bits[i] = lhs.bits[i] | rhs.bits[i];
}
return result;
}
bit operator==(num lhs, num rhs)
{
bit result{-1};
for (int i = 0; i < 16; i++)
{
if (lhs.bits[i].is_stpd() && rhs.bits[i].is_stpd())
continue;
if (lhs.bits[i].is_stpd())
lhs.bits[i] = zero;
if (rhs.bits[i].is_stpd())
rhs.bits[i] = zero;
bit eq = (lhs.bits[i] == rhs.bits[i]);
if (result.is_stpd())
result = eq;
else
result = result & eq;
}
return result;
}
}
namespace circuit_helpers
{
using num_store::num;
using bit_store::bit;
using bit_mani::strm;
using bit_mani::operator&, bit_mani::operator^, bit_mani::operator|, bit_mani::operator==;
using num_mani::operator+, num_mani::operator&, num_mani::operator|, num_mani::operator==;
int run(int la, int lb, int ops[], int opers[][2], int outputs[][16])
{
bit_mani::strm = bit_mani::io_bits(la + lb);
int n = la / 32;
vector<num> aweight(n);
for (int i = 0; i < n; i++)
aweight[i].init_input(16);
vector<num> aposi(n);
for (int i = 0; i < n; i++)
aposi[i].init_input(16);
vector<vector<bit>> g(n, vector<bit>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j].v = strm.input_ptr++;
assert(strm.input_ptr == strm.input_size);
vector<num> tresult(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
tresult[j] = tresult[j] + (aweight[i] & g[i][j]);
vector<num> result(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
num jn;
jn.init_value(j);
result[i] = result[i] + (tresult[j] & (aposi[i] == jn));
}
}
return strm.write(ops, opers, outputs, result);
}
}
// 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])
{
return circuit_helpers::run(la, lb, operations, operands, outputs_circuit);
}
