#include "vision.h"
#include <bits/stdc++.h>
struct Diag {
std::vector <std::pair <int, int>> a;
Diag(const std::set <std::pair <int, int>>& st) {
for (const auto& p : st) {
a.emplace_back(p);
}
}
int ind_or;
int ind_xor;
int ind_not_xor;
int ind_has_two;
};
constexpr bool ok(int i, int j, int n, int m) {
return i >= 0 && j >= 0 && i < n && j < m;
}
std::vector <int> conv(int m, const std::vector <std::pair <int, int>>& a) {
std::vector <int> res(a.size());
for (int i = 0; i < (int) a.size(); i++) {
res[i] = a[i].first * m + a[i].second;
}
return res;
}
void construct_network(int n, int m, int k) {
std::vector <Diag> up, down;
{
std::set <std::pair <int, int>> st;
st.insert({ 0, 0 });
while (st.size()) {
down.push_back(Diag(st));
std::set <std::pair <int, int>> stt;
for (auto p : st) {
if (ok(p.first + 1, p.second, n, m)) stt.insert({ p.first + 1, p.second });
if (ok(p.first, p.second + 1, n, m)) stt.insert({ p.first, p.second + 1 });
}
st = stt;
}
}
{
std::set <std::pair <int, int>> st;
st.insert({ n - 1, 0 });
while (st.size()) {
up.push_back(Diag(st));
std::set <std::pair <int, int>> stt;
for (auto p : st) {
if (ok(p.first - 1, p.second, n, m)) stt.insert({ p.first - 1, p.second });
if (ok(p.first, p.second + 1, n, m)) stt.insert({ p.first, p.second + 1 });
}
st = stt;
}
}
for (Diag& d : down) {
d.ind_or = add_or(conv(m, d.a));
d.ind_xor = add_xor(conv(m, d.a));
d.ind_not_xor = add_not(d.ind_xor);
d.ind_has_two = add_and({ d.ind_or, d.ind_not_xor });
}
for (Diag& d : up) {
d.ind_or = add_or(conv(m, d.a));
d.ind_xor = add_xor(conv(m, d.a));
d.ind_not_xor = add_not(d.ind_xor);
d.ind_has_two = add_and({ d.ind_or, d.ind_not_xor });
}
//{ not xor { or } } and { or }
//or
//or { d.ind_has_two }
auto go = [] (const std::vector <Diag>& diag, int kk) -> int {
std::vector <int> inds;
std::vector <Diag> cur;
for (const Diag& d : diag) {
cur.push_back(d);
if ((int) cur.size() > kk) {
cur.erase(cur.begin());
}
assert((int) cur.size() <= kk);
if ((int) cur.size() == kk) {
std::vector <int> idx;
for (const Diag& dd : cur) {
idx.push_back(dd.ind_or);
}
int ind_or = add_or(idx);
int ind_xor = add_xor(idx);
int ind_not_xor = add_not(ind_xor);
int ind_and = add_and({ ind_not_xor, ind_or });
idx.clear();
for (const Diag& dd : cur) {
idx.push_back(dd.ind_has_two);
}
int ind_h2_or = add_or(idx);
inds.push_back(add_or({ ind_and, ind_h2_or }));
}
}
return add_or(inds);
};
int ind_kp1_up = go(up, k + 1);
int ind_kp1_down = go(down, k + 1);
int ind_kp0_up = go(up, k);
int ind_kp0_down = go(down, k);
int ind_kp1_both = add_and({ ind_kp1_up, ind_kp1_down });
int ind_kp0_both = add_and({ ind_kp0_up, ind_kp0_down });
int ind_kp0_not = add_not(ind_kp0_both);
add_and({ ind_kp1_both, ind_kp0_not });
}
