#include "vision.h" #include<bits/stdc++.h> using namespace std; int n, m, k; int gid(int x, int y){ return x * m + y; } namespace sub125{ void solve(){ int cnt = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int x = i; x < n && x - i <= k; x++){ int d = k - x + i, y = j - d; if(y > -1){ cnt++; add_and({gid(i, j), gid(x, y)}); } if((y = j + d) < m){ cnt++; add_and({gid(i, j), gid(x, y)}); } } } } vector<int>p(cnt); iota(p.begin(), p.end(), n * m); add_or(p); } } namespace sub3{ void solve(){ vector<int>p; for(int i = 0, cnt = n * m - 1; i < n; i++){ for(int j = 0; j < m; j++){ vector<int>s; for(int x = i; x < n && x - i <= k; x++){ int d = k - x + i, y = j - d; if(y > -1){ s.push_back(gid(x, y)); } if((y = j + d) < m){ s.push_back(gid(x, y)); } } if(!s.empty()){ add_or(s); add_and({gid(i, j), cnt + 1}); p.push_back(cnt += 2); } } } add_or(p); } } namespace sub7{ void solve(){ int id = n * m - 1; vector<int>row(n), col(m); for(int i = 0; i < n; row[i++] = ++id){ vector<int>p(m); for(int j = 0; j < m; j++){ p[j] = gid(i, j); } add_or(p); } for(int i = 0; i < m; col[i++] = ++id){ vector<int>p(n); for(int j = 0; j < n; j++){ p[j] = gid(j, i); } add_or(p); } add_or(row); add_xor(row); add_and({id + 1, id + 2}); int one_row = (id += 3); vector<int>p; for(int i = 1; i < m; i++, p.push_back(++id)){ add_and({col[i - 1], col[i]}); } add_or(p); add_and({++id, one_row}); one_row = ++id; add_or(col); add_xor(col); add_and({id + 1, id + 2}); p.clear(); int one_col = (id += 3); for(int i = 1; i < n; i++, p.push_back(++id)){ add_and({row[i - 1], row[i]}); } add_or(p); add_and({++id, one_col}); add_or({++id, one_row}); } } namespace sub468{ int id; void work(vector<int>& val){ for(int bit = 7, N = val.size(); bit > -1; bit--){ if((1 << bit) <= N){ int have_1 = ++id; vector<int>p(val.begin(), val.begin() + (1 << bit)); add_or(p); add_not(id++); for(int i = 0; i + (1 << bit) < N; val[i++] = (id += 3)){ add_and({val[i], have_1}); add_and({val[i + (1 << bit)], have_1 + 1}); add_or({id + 1, id + 2}); } for(int i = N - (1 << bit); i < N; val[i++] = ++id){ add_and({val[i], have_1}); } } } } void solve(){ id = n * m - 1; vector<int>row(n - 1), col(m - 1); for(int i = 0; i + 1 < n; row[i++] = ++id){ vector<int>p(m); for(int j = 0; j < m; j++){ p[j] = gid(i, j); } if(i > 0){ p.push_back(row[i - 1]); } add_xor(p); } for(int i = 0; i + 1 < m; col[i++] = ++id){ vector<int>p(n); for(int j = 0; j < n; j++){ p[j] = gid(j, i); } if(i > 0){ p.push_back(col[i - 1]); } add_xor(p); } work(row); work(col); if(k == --n + --m){ for(int& i : col){ row.push_back(i); } add_and(row); return; } vector<int>p; if(k <= n){ if(k == n){ if(m > 0){ add_not(col[0]); add_and({row[n - 1], id + 1}); p.push_back(id += 2); } else{ p.push_back(row[n - 1]); } } else if(m > 0){ add_not(col[0]); add_xor({row[k - 1], row[k]}); add_and({id + 1, id + 2}); p.push_back(id += 3); } else{ add_xor({row[k - 1], row[k]}); p.push_back(++id); } } else if(n > 0){ int _k = k - n; add_xor({col[_k - 1], col[_k]}); add_and({id + 1, row[n - 1]}); p.push_back(id += 2); } if(k <= m){ if(k == m){ if(n > 0){ add_not(row[0]); add_and({col[m - 1], id + 1}); p.push_back(id += 2); } else{ p.push_back(col[m - 1]); } } else if(n > 0){ add_not(row[0]); add_xor({col[k - 1], col[k]}); add_and({id + 1, id + 2}); p.push_back(id += 3); } else{ add_xor({col[k - 1], col[k]}); p.push_back(++id); } } else if(m > 0){ int _k = k - m; add_xor({row[_k - 1], row[_k]}); add_and({id + 1, col[m - 1]}); p.push_back(id += 2); } for(int i = 1; i < n; i++){ int j = k - i; if(j > 0 && j < m){ add_xor({row[i - 1], row[i]}); add_xor({col[j - 1], col[j]}); add_and({id + 1, id + 2}); p.push_back(id += 3); } } add_or(p); } } void construct_network(int _n, int _m, int _k){ k = _k; if(max(n = _n, m = _m) <= 10 || min(n, m) == 1){ return sub125::solve(); } if(max(n, m) <= 30){ return sub3::solve(); } if(k == 1){ return sub7::solve(); } return sub468::solve(); }