ありえる座標の最大値を \(M\) とします。今回の制約では \(M=100\) です。

整数の組 \((i,j,k)\) に対し \(2\) 点 \((i,j,k),(i+1,j+1,k+1)\) を結ぶ線分を対角線とする立方体を「小立方体 \((i,j,k)\)」と呼ぶことにします。また座標を気にしないとき単に「小立方体」と呼びます。

\(2\) つの直方体 \(i,j\) が面で隣接するための必要十分条件は、直方体 \(i\) に含まれるある小立方体と、直方体 \(j\) に含まれるある小立方体が上下左右前後のいずれかの向きで隣り合っていることです。

よって、直方体のペアではなく、小立方体のペアを全て調べれば問題を解くことができます。 具体的には次のような手順で解けます。

• \(M\times M\times M\) の配列を用意し、\(0\leq i,j,k<M\) である各 \((i,j,k)\) について、小立方体 \((i,j,k)\) がどの直方体に含まれるかを記録する
• 全ての小立方体に対し、自身及び自身と隣接する小立方体がそれぞれがどの直方体に含まれているかを調べ、結果(面で接する直方体のペア)を set などで保持する

小立方体は \(O(M^3)\) 個あり、各小立方体に隣接する小立方体は高々 \(6\) 個であることから、隣接する小立方体のペア全てはを調べることは \(O(M^3)\) 時間でできます。結果の保持を set や 配列+unique などで行うと \(O(M^3\log N)\) で答えを求めることができます。hash set を用いると expected \(O(M^3)\) になります。

Writer解(C++)