Sorting
시간 제한1초메모리 제한1024 MB
숨겨진 1부터 N까지의 순열을 복원합니다. 위치의 대소를 묻는 질문은 최대한 적게 쓰고, 두 위치 값의 차이가 d로 나누어지는지 묻는 질문은 횟수 제한 없이 사용합니다.
문제
Sashka는 온라인 프로그래밍 대회에 정기적으로 참가한다. 이번 대회의 상품은 몰디브에서 열리는 여름 프로그래밍 캠프 참가권이다. 이 대회를 위해 Sashka는 사용자 이름을 Sorting으로 설정했다. 과제 중 하나는 다음과 같다:
심사위원이 1부터 N까지의 수로 이루어진 순열 p_1, p_2, p_3, ..., p_N을 골랐다. 이 순열을 복원하려면 심사위원에게 두 종류의 질문을 할 수 있다:
- 두 위치 x, y (1 ≤ x, y ≤ N)가 주어졌을 때, p_x < p_y가 참인가?
- 수 d와 두 위치 x, y (1 ≤ x, y, d ≤ N)가 주어졌을 때, |p_x − p_y| ≡ 0 (mod d)가 참인가? 즉, x번째 위치와 y번째 위치의 원소 차이가 d로 나누어떨어지는가?
첫 번째 종류의 질문은 가능한 한 적게 해야 한다 (아래 채점 항목 참고). 두 번째 종류의 질문은 횟수에 제한이 없다.
N이 주어졌을 때 순열을 복원하는 프로그램 sorting을 작성하여 Sashka를 도와라. 프로그램에는 solve 함수가 포함되어야 하며, 이 함수는 심사위원의 프로그램과 함께 컴파일되어 실행된다.
제한
2 ≤ N ≤ 500,000 모든 1 ≤ i ≤ N에 대해 1 ≤ p_i ≤ N 모든 1 ≤ i < j ≤ N에 대해 p_i ≠ p_j