(x,y)(1x<yN)(x,y)(1 \le x \lt y \le N) の組を固定した場合にそれが条件を満たすかどうか判定することを考えます。

ai,j=a_{i,j}= - のとき 2i2^i の bit を立てた整数 bjb_jai,j=a_{i,j}= o のとき 2i2^i の bit を立てた整数 cjc_j を定義すると、問題文の条件は bx&cy,cx&by,cx&cyb_x \& c_y,c_x \& b_y,c_x \& c_y の全てが 00 であることと同値です(ただし、&\& は bit ごとの論理積を表します)。

bj,cjb_j,c_j をそれぞれ std::bitset や多倍長整数で管理することでこの問題を解くことができます。計算量は O(N3wordsize)O(\frac{N^3}{\mathrm{wordsize}}) です。