An Animal Contest 7 P4 - Squirrel Shenanigans

Points: 20

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

After a separate mission, Tony has uncovered the hidden plans of the invading squirrel army. In an attempt to halt all communication on Earth — for an easier conquest — the squirrels are employing secret technologies to flood Discord with Nitro scams. These scams rely on users clicking into suspicious links (after being offered free Nitro, of course) and using their phones to scan QR codes, where then the real shenanigans start. The squirrels will then hijack the user's account and block all their friends after sending them the exact same scam message. Luckily, Tony has found a way to neutralize the threat:

There is a secret permutation $a$ ~a~ of $1, 2, \dots, N$ ~1, 2, \dots, N~ where the $i$ ~i~-th element is denoted as $a_i$ ~a_i~. What it does, you have no idea — you're just going to have to trust. You are given a QR code represented by an $N \times N$ ~N \times N~ binary matrix $m$ ~m~, which will help you find $a$ ~a~. The cell in the $i$ ~i~-th row from the top and $j$ ~j~-th column from the left is denoted as $m_{i,j}$ ~m_{i,j}~. An operation is defined as choosing some index $i$ ~i~ $(1 < i < N)$ ~(1 < i < N)~ and replacing $a_i$ ~a_i~ with the median of $a_{i-1}, a_i, a_{i+1}$ ~a_{i-1}, a_i, a_{i+1}~. If $m_{i,j} = 1$ ~m_{i,j} = 1~, it is possible to perform some number of operations (possibly none) on $a$ ~a~ and have $a_i = j$ ~a_i = j~. If $m_{i,j} = 0$ ~m_{i,j} = 0~, this is impossible.