합과 XOR의 대화

가능한 모든 정수 쌍을 그래프로 나타내자.

왼쪽에는 가능한 합 $s$마다 정점 $S_s$를 만든다. 오른쪽에는 가능한 XOR 값 $y$마다 정점 $Y_y$를 만든다. 가능한 쌍 $(a,b)$마다 $S_{a+b}$와 $Y_{a\mathbin{\mathrm{xor}}b}$를 잇는 간선을 하나 만든다.

어떤 날이 시작될 때 남아 있는 간선들은 이전 날까지의 모든 선언과 모순되지 않는 쌍들이다. 다다스가 관찰한 합에 대응하는 정점의 차수가 $1$이면 다다스는 두 수를 유일하게 알 수 있다. 모그도 같은 방식으로 XOR 정점의 차수가 $1$일 때 두 수를 알 수 있다.

두 사람은 동시에 말하므로, 한 날에는 시작 시점의 차수가 $1$인 정점에 닿은 모든 간선을 동시에 제거해야 한다. 따라서 정답은 실제 간선이 제거되는 라운드 번호이다. 끝까지 제거되지 않고 그래프의 $2$-core에 남으면 정답은 $-1$이다.

$X\ge 10$인 경우를 분석한다. $P$를 $X$ 이하의 가장 큰 $2$의 거듭제곱이라 하자.

합 정점의 초기 차수가 $1$인 경우는 다음 네 개뿐이다.

• 합이 $3$인 $(1,2)$.
• 합이 $4$인 $(1,3)$.
• 합이 $2X-2$인 $(X-2,X)$.
• 합이 $2X-1$인 $(X-1,X)$.

초기 XOR 정점의 차수가 $1$인 경우는 다음과 같이 분류된다.

• $X=P$이면 $(i,P)$가 모든 $1\le i<P$에 대해 유일하다.
• $X=P+1$이면 $(1,P)$와 $(1,P+1)$만 유일하다.
• 그 외에는 없다.

이를 보이기 위해 XOR 값 $y$를 생각하자. $y<P$이면 최상위 비트가 바뀌지 않는다. $P\ge 8$인 범위에서는 같은 XOR 값을 만드는 쌍을 낮은 구간에서 적어도 두 개 만들 수 있다.

$y\ge P$이면 $y=P+z$로 쓸 수 있다. 높은 쪽 수를 $P+t$라 하면 낮은 쪽 수는 $t\mathbin{\mathrm{xor}}z$이다. 여기서 $0\le t\le X-P$이다. $t=z$일 때만 낮은 쪽 수가 $0$이 되어 사용할 수 없다.

• $X-P=0$이면 가능한 $t$가 하나뿐이므로 $(z,P)$가 유일하다.
• $X-P=1$이면 $z=0,1$에서만 하나가 남고, 각각 $(1,P+1)$과 $(1,P)$이다.
• $X-P\ge 2$이면 하나를 제외해도 적어도 두 개가 남는다.

이제 매 라운드에서 새로 차수가 $1$이 되는 정점을 조사하면 다음 표를 얻는다.

$X=P$일 때 첫 라운드에서 $(i,P)$가 모두 제거된다. 이 때문에 합 $2P-4$와 $2P-3$에서 각각 $(P-3,P-1)$과 $(P-2,P-1)$만 남아 둘째 날 제거된다.

$X=P+1$일 때 첫 라운드 뒤 XOR $2P-2$에서 $(P-2,P)$만 남는다. 이 간선이 제거되면 합 $2P-2$에서 $(P-3,P+1)$만 남는다. 다시 이 간선이 제거되면 XOR $2P-4$에서 $(P-4,P)$만 남는다.

표에 적힌 간선을 제거한 뒤에는 양의 차수를 가진 모든 합 정점과 XOR 정점의 차수가 적어도 $2$이다. 이는 경계에서 거리가 일정한 작은 경우만 직접 확인하고, 나머지 경우에는 합을 유지하는 인접한 쌍 또는 같은 XOR 값을 만드는 다른 $t$를 선택하여 확인할 수 있다. $X\ge 10$이라는 조건 때문에 필요한 수들이 범위 안에 남는다. 따라서 더 이상의 제거는 일어나지 않는다.

$X\le 9$에서는 위 증명에 사용한 여유가 부족하여 추가 연쇄가 생길 수 있다. 가능한 간선이 최대 $\binom{9}{2}=36$개뿐이므로 그래프를 직접 만들고 라운드별로 시뮬레이션한다.

각 테스트 케이스에서 $P$를 구하는 데 $O(\log X)$가 걸린다. 작은 경우의 시뮬레이션 크기는 상수이므로 전체 시간 복잡도는 $O(T\log X)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5.6