Nostalgiabait

$X \geq 0$인 경우를 먼저 생각하자. $X<0$인 경우에는 $|X|$에 대한 배치를 만든 뒤 행과 열을 서로 바꾸면 $M_1$과 $M_2$가 서로 바뀌므로 처리할 수 있다.

각 행에는 서로 다른 양의 정수 $N$개가 있으므로 그 행의 최댓값은 적어도 $N$이다. 따라서 $M_2 \geq N$이다. 한편 $N$개의 행 최댓값은 서로 다른 수이므로 그 최솟값은 $$ 이하이다. 따라서

$$N \leq M_2 \leq N^2-N+1.$$

같은 논리로

$$N \leq M_1 \leq N^2-N+1.$$

따라서 반드시

$$|X| \leq (N^2-N+1)-N=(N-1)^2$$

이어야 한다.

이제 $0 \leq X \leq (N-1)^2$라 하자. $K=N^2-N+1$로 둔다.

먼저

$$H_{1,1}=K-X$$

로 둔다. 그리고 $2 \leq i \leq N$에 대해

$$H_{i,i}=K+i-1$$

로 둔다. 즉, 가장 큰 $N-1$개의 수 $K+1,K+2,\cdots,N^2$를 대각선에 배치한다.

$X>0$이면 추가로

$$H_{2,1}=K$$

로 둔다. 아직 값이 정해지지 않은 칸은 왼쪽 위부터 오른쪽 아래 순서로 보면서, 아직 사용하지 않은 가장 작은 양의 정수를 넣는다.

$X>0$일 때 $K-X \geq N$이다. 따라서 첫째 행의 나머지 $N-1$칸에는 모두 $K-X$보다 작은 수가 들어가며, 첫째 행의 최댓값은 이다. 둘째 행부터는 대각선에 둔 값이 그 행의 최댓값이므로

$$M_2=K-X.$$

첫째 열에는 $K$가 있고, 나머지 열에는 각각 $K+1,K+2,\cdots,N^2$ 중 하나가 있으므로

$$M_1=K.$$

따라서 $M_1-M_2=X$이다.

$X=0$이면 $H_{1,1}=K$이고, 각 행과 열의 최댓값 중 최솟값이 모두 $K$이므로 역시 조건을 만족한다.

그러므로 가능한 경우는 정확히 $|X| \leq (N-1)^2$인 경우이다. 각 칸을 한 번씩 채우면 되므로 시간 복잡도는 테스트 케이스 전체에 대해 $O\left(\sum N^2\right)$이다.

Solution written by GPT5.6