Let \(M\) be the maximum absolute coordinate. In our constraints, \(M=100\).

For an integer tuple \((i,j,k)\), we denote by “cube \((i,j,k)\)” the cube whose diagonal is the segment connecting two points \((i,j,k)\) and \((i+1,j+1,k+1)\). If we do not care about its coordinates, we simply call it a “cube.”

Two cuboids \(i\) and \(j\) share a surface if and only if a cube contained in cuboid \(i\) and another in cuboid \(j\) are adjacent in one of the three directions.

Thus, it is sufficient to inspect all pairs of cubes, instead of cuboids. Specifically, it can be solved as follows.

• Prepare an \(M\times M\times M\) array. For each \(0\leq i,j,k<M\), record which cuboids contain cube \((i,j,k)\).
• For all cubes, check which cuboids contain the cube itself and adjacent cube, and maintain the results (pairs of adjacent cuboids) in a set.

There are \(O(M^3)\) cubes, and each cube has at most six cubes adjacent to it, so inspecting all pairs of adjacent cubes can be done in a total of \(O(M^3)\). If we use a set or an array + unique to maintain the result, the answer can be found in a total of \(O(M^3\log N)\) time. If you use a hash set, it reduces to expected \(O(M^3)\) time.

Writer’s solution (C++)