/**
* Wow. Idk how to express my shock when i saw that interactive problems can be like
* this! So we basically have to write a program that outputs the correct 0/1 across
* all images. First thought: we can't do compare each pair of rows, this takes about
* 19900 (>10000) calls.
* We don't have "for" or "if" statements... Hmm. I don't wanna do int addition /
* subtraction using logic gates too... Well, in general we don't have much calls
* available, so perhaps in a lot of calls the num of input isn't small. Nah...
*
* I'd like to note down my final thought. Suppose that c_1, c_2, ..., c_m are 0/1
* bits representing whether column i has a black cell. Let's put away the case of
* only one 1. Let d_i := c_1 ^ c_2 ^ ... ^ c_i, so the number of 1s in (d_i) is
* the horizontal dist. Similarly we can do this for the vertical direction, then
* it suffices to count the num of 1s in some cells and check if it's K.
* Unfortunately, the only sol i have is to do a dp which requires an additional
* K(H+W) cells. Too much... (I'll submit a brute-force version in impl1)
*
* This think this is a problem where scoring partials is easy, but getting full is
* hard. Tinjyu gave a hint during our IOI 2022 training: consider diagonals. Take
* K=1 as an example. We know that if num of calls is O(HW) we definitely fail, but
* if it's O(HW) we have a large const. factor to play with (since num of calls is
* the bottleneck). So, take OR on each diagonal and take AND on adjacent diagonals.
* Notice that if two cells' Manhattan dist. is 1, exactly 2 pairs of adjacent
* diagonals have 1 in their ANDs.
*
* We can generalize this approach. Assume that the two cells are u, v. We draw two
* diagonals through u and two diagonals through v; since in each direction there
* are exactly 2 diagonals, the max of dist. between diagonals in the same direction
* would be their Manhattan dist. I guess this may be inspired by the fact that cells
* whose dist. to a fixed cell form the border of a rotated square.
* This is so beautiful (!), though i can hardly believe that I would be able to come
* up with sth like this! In some way, it's like rotating the grid by 45deg,
* transforming Manhattan into Chebyschef.
*
* Number of calls: 5(H+W) (idk if 5 is correct, but it must be O(H+W))
* Number of reads: (idk, but not too many)
* Implementation 1 (Solves [S1-3], [S5], [S6])
*/
#include <bits/stdc++.h>
#include "vision.h"
typedef std::vector<int> vec;
void construct_network(int h, int w, int K) {
vec d1s, d2s;
for (int d = 0; d <= h + w - 2; d++) {
vec diag_cells;
for (int i = 0; i < h; i++) {
int j = d - i;
if (0 <= j && j < w)
diag_cells.push_back(i * w + j);
}
assert(!diag_cells.empty());
d1s.push_back(add_or(diag_cells));
}
for (int d = -w + 1; d <= h - 1; d++) {
vec diag_cells;
for (int i = 0; i < h; i++) {
int j = i - d;
if (0 <= j && j < w)
diag_cells.push_back(i * w + j);
}
assert(!diag_cells.empty());
d2s.push_back(add_or(diag_cells));
}
int diags = h + w - 1;
// We proceed in two parts. First checking whether the pairs in d1s and d2s
// have dist. <= K, then we check whether there's one = K.
vec greater_check; // should be all 0
for (int i = 0; i < diags; i++) {
vec neighb1, neighb2;
for (int j = 0; j < diags; j++) {
int dist = std::abs(i - j);
if (dist > K) {
neighb1.push_back(d1s[j]);
neighb2.push_back(d2s[j]);
}
}
if (!neighb1.empty())
greater_check.push_back(add_and({add_or(neighb1), d1s[i]}));
if (!neighb2.empty())
greater_check.push_back(add_and({add_or(neighb2), d2s[i]}));
}
int part1_flag;
if (!greater_check.empty())
part1_flag = add_not(add_or(greater_check));
else
part1_flag = -1;
vec equal_check;
for (int i = 0; i < diags; i++) {
vec neighb1, neighb2;
if (i + K < diags) {
neighb1.push_back(d1s[i + K]);
neighb2.push_back(d2s[i + K]);
}
if (i - K >= 0) {
neighb1.push_back(d1s[i - K]);
neighb2.push_back(d2s[i - K]);
}
if (!neighb1.empty())
equal_check.push_back(add_and({add_or(neighb1), d1s[i]}));
if (!neighb2.empty())
equal_check.push_back(add_and({add_or(neighb2), d2s[i]}));
}
assert(!equal_check.empty());
int part2_flag = add_or(equal_check); // if part1_flag is -1 this is the ans
if (part1_flag != -1)
add_and({part1_flag, part2_flag}); // ans
}
