#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
// Alice
int // returns la
alice(
/* in */ const int n,
/* in */ const char names[][5],
/* in */ const unsigned short numbers[],
/* out */ bool outputs_alice[]
) {
// outputs_alice[0] = 1;
// outputs_alice[1] = 0;
// return 2;
for(int i = 0; i < 16; i++) {
outputs_alice[i] = ((1 << i) & numbers[0]) >> i;
}
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[]
) {
// outputs_bob[0] = 1;
// outputs_bob[1] = 1;
// outputs_bob[2] = 0;
// return 3;
for(int i = 0; i < m; i++) {
outputs_bob[i] = 1;
}
return m;
}
// 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]
) {
// operations[5] = 8;
// operations[6] = 14;
// operands[5][0] = 0; operands[5][1] = 4;
// operands[6][0] = 2; operands[6][1] = 5;
// int final_results[] = {20000, 0, 24464};
// for(int i = 0; i < 3; ++i)
// for(int j = 0; j < 16; ++j)
// outputs_circuit[i][j] = 5 + (final_results[i] >> j & 1);
// return 7;
/*
full adder:
- carry bit
- previous answer stored where?
- m
prev_ans[i] = prev_ans[i] XOR prev_ans[i - offset] XOR carry
carry = (prev_ans[i] * prev_ans[i - offset]) + carry(prev_ans[i] + prev_ans[i - offset])
*/
auto full_adder = [&](vector<int> prev_ans, vector<int> add_what, int la, int lb, int carry, int &cnt, int return_what) -> vector<int> {
vector<int> answers_this_time(16);
for(int j = 0; j < 16; j++) {
operations[cnt] = OP_XOR;
operands[cnt][0] = prev_ans[j];
operands[cnt][1] = add_what[j];
cnt += 1;
operations[cnt] = OP_XOR;
operands[cnt][0] = carry;
operands[cnt][1] = cnt - 1;
answers_this_time[j] = cnt;
cnt += 1;
operations[cnt] = OP_OR;
operands[cnt][0] = prev_ans[j];
operands[cnt][1] = add_what[j];
cnt += 1;
operations[cnt] = OP_AND;
operands[cnt][0] = carry;
operands[cnt][1] = cnt - 1;
cnt += 1;
operations[cnt] = OP_AND;
operands[cnt][0] = prev_ans[j];
operands[cnt][1] = add_what[j];
cnt += 1;
operations[cnt] = OP_OR;
operands[cnt][0] = cnt - 2;
operands[cnt][1] = cnt - 1;
carry = cnt;
cnt += 1;
}
for(int j = 0; j < 16; j++) {
// if cur bit is 0, keep prev_ans
// cout << "cnt = " << cnt << "\n";
operations[cnt] = OP_GREATER;
operands[cnt][0] = prev_ans[j];
operands[cnt][1] = return_what;
cnt += 1;
// if cur bit is 1, keep new ans
operations[cnt] = OP_AND;
operands[cnt][0] = answers_this_time[j];
operands[cnt][1] = return_what;
cnt += 1;
operations[cnt] = OP_OR;
operands[cnt][0] = cnt - 2;
operands[cnt][1] = cnt - 1;
prev_ans[j] = cnt;
cnt += 1;
}
return prev_ans;
};
int cnt = la + lb;
vector<int> prev_ans(16);
vector<int> add_what(16);
for(int i = 0; i < 16; i++) {
add_what[i] = i;
}
for(int i = cnt; i < cnt + 16; i++) {
operations[i] = OP_ZERO;
operands[i][0] = 0;
operands[i][1] = 0;
prev_ans[i - cnt] = i;
}
cnt += 16;
int carry = cnt;
operations[cnt] = OP_ZERO;
operands[cnt][0] = 0;
operands[cnt][1] = 0;
cnt += 1;
for(int i = 0; i < lb; i++) {
prev_ans = full_adder(prev_ans, add_what, la, lb, carry, cnt, 1);
}
// for(int i = la; i < la + lb; i++) {
// int offset = i - la;
// vector<int> answers_this_time(16);
// for(int j = 0; j < 16; j++) {
// if(offset > j) {
// operations[cnt] = OP_X0;
// operands[cnt][0] = prev_ans[j];
// operands[cnt][1] = 0;
// answers_this_time[j] = cnt;
// cnt += 1;
// }
// else {
// operations[cnt] = OP_XOR;
// operands[cnt][0] = prev_ans[j];
// operands[cnt][1] = j - offset;
// cnt += 1;
// operations[cnt] = OP_XOR;
// operands[cnt][0] = carry;
// operands[cnt][1] = cnt - 1;
// answers_this_time[j] = cnt;
// cnt += 1;
// operations[cnt] = OP_OR;
// operands[cnt][0] = prev_ans[j];
// operands[cnt][1] = j - offset;
// cnt += 1;
// operations[cnt] = OP_AND;
// operands[cnt][0] = carry;
// operands[cnt][1] = cnt - 1;
// cnt += 1;
// operations[cnt] = OP_AND;
// operands[cnt][0] = prev_ans[j];
// operands[cnt][1] = j - offset;
// cnt += 1;
// operations[cnt] = OP_OR;
// operands[cnt][0] = cnt - 2;
// operands[cnt][1] = cnt - 1;
// carry = cnt;
// cnt += 1;
// }
// }
// for(int j = 0; j < 16; j++) {
// // if cur bit is 0, keep prev_ans
// // cout << "cnt = " << cnt << "\n";
// operations[cnt] = OP_GREATER;
// operands[cnt][0] = prev_ans[j];
// operands[cnt][1] = i;
// cnt += 1;
// // if cur bit is 1, keep new ans
// operations[cnt] = OP_AND;
// operands[cnt][0] = answers_this_time[j];
// operands[cnt][1] = i;
// cnt += 1;
// operations[cnt] = OP_OR;
// operands[cnt][0] = cnt - 2;
// operands[cnt][1] = cnt - 1;
// prev_ans[j] = cnt;
// cnt += 1;
// }
// operations[cnt] = OP_ZERO;
// operands[cnt][0] = 0;
// operands[cnt][1] = 0;
// carry = cnt;
// cnt += 1;
// // cout << "iteration: " << i - la << "\n";
// // for(int j = 0; j < 16; j++) {
// // cout << "jth bit stored: " << prev_ans[j] << "\n";
// // }
// }
for(int j = 0; j < 16; j++) {
outputs_circuit[0][j] = prev_ans[j];
}
return cnt;
}
