순열 만들기
시간 제한2초메모리 제한128 MB
N, M, K가 주어질 때 최장 증가 부분수열 길이가 M이고 최장 감소 부분수열 길이가 K인 순열 중 사전순으로 가장 작은 것과 가장 큰 것을 구성합니다.
문제
1부터 N까지의 정수가 각각 한 번씩 등장하는 길이 N의 순열을 생각하자. 이 순열에서 일부 원소를 지우고 남은 원소들의 상대적인 순서를 유지하면 부분수열이 된다.
부분수열의 원소가 왼쪽에서 오른쪽으로 갈수록 엄격히 커지면 증가 부분수열이고, 엄격히 작아지면 감소 부분수열이다. 가장 긴 증가 부분수열의 길이를 M, 가장 긴 감소 부분수열의 길이를 K라고 하자.
세 정수 N, M, K가 주어질 때, 길이 N인 순열 중 가장 긴 증가 부분수열의 길이가 정확히 M이고 가장 긴 감소 부분수열의 길이가 정확히 K인 순열을 구하시오.
입력
첫째 줄에 순열의 길이 N, 가장 긴 증가 부분수열의 길이 M, 가장 긴 감소 부분수열의 길이 K가 공백으로 구분되어 주어진다.
1 <= N <= 100000
1 <= M, K <= N
출력
조건을 만족하는 순열이 존재하지 않으면 첫째 줄에 -1만 출력한다.
존재한다면 첫째 줄에 조건을 만족하는 순열 중 사전순으로 가장 앞서는 순열을 출력하고, 둘째 줄에 사전순으로 가장 뒤에 오는 순열을 출력한다.