프로그램 명: alyona_mex
제한시간: 2 초
Alyona Mom은 Alyona에게 음이 아닌 정수로 이루어져있고 특별한 조건을 만족하는 수열 a를 주고 싶어한다.
Alyona는 변덕이 심하고 까다로워서, 수열을 받은 후에는 m개의 부분수열로 나누어 검사를 한다.
(이 때, 부분수열이라는 것은 본래의 수열에서 어떤 부분을 연속적으로 잘라낸것이다.
i번째 부분수열은 두 정수 li와 ri로 나타낼 수 있는데 이는 a[li] , a[li+1] , ... , a[ri]를 뜻한다)
이번에 그녀는 부분수열들의 mex를 구해보기로 했다. (어떤 집합 S의 mex는 집합 S에 포함되어 있지 않으면서 가장 작은 음이 아닌 정수이다)
부분수열들의 mex 값 중 가장 작은 mex값이 가장 커지는 n개의 원소를 가진 수열을 가지고 싶어 한다.
Alyona Mom을 도와 위와 같은 수열을 구해보자.
입력 형식
첫 줄에는, n과 m이 입력된다 (1≤n,m≤100000).
다음 m줄에는 Alyona가 선택한 부분수열의 정보가 입력된다.
두 정수 li,ri(1≤li≤ri≤n)는 i번째 부분수열이 a[li], a[li+1] , ... , a[ri] 임을 뜻한다.
출력 형식
첫 줄에는, 가능한 한 최대인 최소 mex를 출력한다.
두 번째 줄에는, 이 때의 수열 a를 출력한다.
a의 모든 원소는 어떠한 입력에도 0과 10^9사이에 있음이 보장된다.
만약 여러개의 답이 있다면, 그 중 어떤 것을 출력해도 상관 없다.
입출력 예
입력
5 3
1 3
2 5
4 5
출력
2
1 0 2 1 0
입력
4 2
1 4
2 4
출력
3
5 2 0 1
참고
첫 번째 데이터에서
부분수열 1 3의 mex는 3이다. 부분수열 2 5의 mex도 3이 된다. 부분수열 4 5의 mex는 2이다.
따라서 mex 중 최소 값은 2이며 어떠한 수열도 이 최소 값을 2보다 크게 할 수 없다.
출처: Codeforces Round #381
[질/답]
[제출 현황]
[푼 후(0)]