문제 배치

$N<3$이거나 E 또는 H가 없으면 불가능하다. 답의 후보 폭 $D$를 이분 탐색한다. E와 H를 각각 정렬한다. 각 종류의 최솟값을 $a$, 최댓값을 $b$라 하자. $b-a\le D$이면 그 종류 전체를 바깥 Div에 남겨도 된다. 그렇지 않으면 바깥 Div에 최솟값과 최댓값을 동시에 남길 수 없다. 최댓값을 남기는 경우 $b-D$ 미만인 모든 문제를 Div.2에 강제로 넣는다. 최솟값을 남기는 경우 $a+D$ 초과인 모든 문제를 Div.2에 강제로 넣는다. 이 두 경우만 확인하면 충분하다. 바깥 Div에 양 극값을 모두 남기면 폭이 $D$를 넘는다. Div.2에 양 극값을 모두 넣어도 폭이 $D$를 넘는다. 따라서 Div.2가 정확히 한 극값을 포함하며, 반대 극값을 남기는 방향의 강제 집합을 모두 포함해야 한다. E와 H의 방향 조합 네 가지를 확인한다. 강제 집합 합집합의 폭이 $D$ 이하이면 Div.2에 넣고 나머지를 각각 Div.3과 Div.1에 넣는다. 각 강제 집합은 반대쪽 극값을 남기므로 두 바깥 Div는 비지 않는다. 강제 집합이 둘 다 비면 $N\ge3$이므로 바깥 Div를 비우지 않으면서 하나를 Div.2로 옮긴다. 서브태스크 1은 각 문제의 허용 Div 두 가지를 모두 탐색하여 $O(2^N N)$ 시간에 푼다. 전체 풀이는 정렬 후 강제 범위 경계를 이분 탐색하여 $O(N\log N+\log V\log N)$ 시간, $O(N)$ 공간을 사용한다. $V$는 난이도 범위이다. 모든 값과 차이는 $10^9$ 이하로 64비트 범위에 충분히 들어간다. Solution written by GPT6.1