#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void construct_network(int n, int m, int k) {
if (n * m == 2) {
add_and({0, 1});
return;
}
const int ZERO = add_and({0, 1, 2});
const int ONE = add_not(ZERO);
function<int(void)> add_zero = [&]() -> int { return add_and({ZERO}); };
function<int(void)> add_one = [&]() -> int { return add_and({ONE}); };
function<int(int, int)> hash = [&](int x, int y) -> int {
return x * m + y;
};
function<bool(int, int)> valid = [&](int x, int y) -> bool {
return ((0 <= x && x < n) && (0 <= y && y < m));
};
// stores position of min in range [st, en]
function<int(int, int)> findmin = [&](int st, int en) -> int {
int diff = en - st + 1;
int prev = add_zero();
for (int i = 1; i < 8; i++) add_zero();
vector<int> allprev;
int prevtakexor = add_zero();
for (int cur = 1; cur <= diff; cur++) { // from min
int pos = st + (cur - 1);
// check if [prev, prev + 8) has value
vector<int> prevs = {prevtakexor};
for (int i = prev; i < prev + 8; i++) prevs.pb(i);
prevtakexor = add_or(prevs);
int takexor = add_not(prevtakexor); // 1 if prev = 0
// assign (pos & takexor & (cur & (1 << i))) to prev
int nxt = -1;
for (int i = 0; i < 8; i++) {
int res = add_and({pos, takexor, (bool(cur & (1 << i)) ? ONE : ZERO)});
if (nxt == -1) nxt = res;
}
prev = nxt;
allprev.pb(nxt);
}
// only 1 has value, take or
int ret = -1;
for (int i = 0; i < 8; i++) {
vector<int> v;
for (int &x : allprev) v.pb(x + i);
int res = add_or(v);
if (ret == -1) ret = res;
}
return ret;
};
// stores position of max in range [st, en]
function<int(int, int)> findmax = [&](int st, int en) -> int {
int diff = en - st + 1;
int prev = add_zero();
for (int i = 1; i < 8; i++) add_zero();
vector<int> allprev;
int prevtakexor = add_zero();
for (int cur = diff; cur >= 1; cur--) { // from max
int pos = st + (cur - 1);
// check if [prev, prev + 8) has value
vector<int> prevs = {prevtakexor};
for (int i = prev; i < prev + 8; i++) prevs.pb(i);
prevtakexor = add_or(prevs);
int takexor = add_not(prevtakexor); // 1 if prev = 0
// assign (pos & takexor & (cur & (1 << i))) to prev
int nxt = -1;
for (int i = 0; i < 8; i++) {
int res = add_and({pos, takexor, (bool(cur & (1 << i)) ? ONE : ZERO)});
if (nxt == -1) nxt = res;
}
prev = nxt;
allprev.pb(nxt);
}
// only 1 has value, take or
int ret = -1;
for (int i = 0; i < 8; i++) {
vector<int> v;
for (int &x : allprev) v.pb(x + i);
int res = add_or(v);
if (ret == -1) ret = res;
}
return ret;
};
// addition modulo 2^10 = 1024
function<vector<int>(vector<int>, vector<int>)> add = [&](vector<int> lhs, vector<int> rhs) -> vector<int> {
vector<int> res;
int prev = add_zero(); // carrying
res.pb(add_xor({lhs[0], rhs[0]}));
for (int i = 1; i < 10; i++) {
// handle carrying:
// (prev, lhs[i - 1], rhs[i - 1]) >= 2
// (AND = 1) or (XOR = 0 and OR = 1)
// (AND) or (XOR xor OR) (no case where (XOR = 1 and OR = 0))
vector<int> check = {prev, lhs[i - 1], rhs[i - 1]};
int isthree = add_and(check);
int istwo = add_xor({add_xor(check), add_or(check)});
int fincarry = add_or({isthree, istwo});
prev = fincarry;
// calculate current bit
res.pb(add_xor({prev, lhs[i], rhs[i]}));
}
return res;
};
int st = -1, en = -1;
// find vertical
for (int i = 0; i < n; i++) {
vector<int> v;
for (int j = 0; j < m; j++) v.pb(hash(i, j));
int res = add_or(v);
if (i == 0) st = res;
if (i == n - 1) en = res;
}
int vmini = findmin(st, en);
int vmaxi = findmax(st, en);
// find horizontal
for (int i = 0; i < m; i++) {
vector<int> v;
for (int j = 0; j < n; j++) v.pb(hash(j, i));
int res = add_or(v);
if (i == 0) st = res;
if (i == m - 1) en = res;
}
int hmini = findmin(st, en);
int hmaxi = findmax(st, en);
// cerr << vmini << ' ' << vmaxi << ' ' << hmini << ' ' << hmaxi << endl;
// (vmax - vmin) + (hmax - hmin)
// = (vmax + (1023 - vmin)) + (hmax + (1023 - hmin)) + 2 (mod 1024)
// = (vmax + (vmin ^ 1023)) + (hmax + (hmin ^ 1023)) + 2 (mod 1024)
vector<int> vmax(10), vmin(10), hmax(10), hmin(10);
vector<int> two(10);
for (int i = 0; i < 10; i++) {
// take xor with mins
vmax[i] = (i < 8 ? vmaxi + i : ZERO);
vmin[i] = (i < 8 ? add_not(vmini + i) : ONE);
hmax[i] = (i < 8 ? hmaxi + i : ZERO);
hmin[i] = (i < 8 ? add_not(hmini + i) : ONE);
two[i] = (i == 1 ? ONE : ZERO);
}
vector<int> res1 = add(vmax, vmin);
vector<int> res2 = add(hmax, hmin);
vector<int> dist = add(add(res1, res2), two);
// compare dist and k
vector<int> fin;
for (int i = 0; i < 10; i++) {
fin.pb(add_xor({dist[i], (bool(k & (1 << i)) ? ONE : ZERO)}));
}
add_not(add_or(fin));
}
