순열 복원

시간 제한2초메모리 제한512 MB

요약
배열 a와 b가 주어질 때, a[i]는 i에서 끝나는 가장 긴 증가 부분 수열의 길이, b[i]는 i에서 시작하는 가장 긴 감소 부분 수열의 길이가 되도록 순열 p를 만든다.
난이도

어려움10점 중 8점

유형
그리디, 정렬, 배열, 조합론
정답자
아직 제출이 없습니다

문제

양의 정수 nn과, 각각 nn개의 정수를 담은 두 배열 aa, bb가 주어진다.

각 i∈{1,2,…,n}i \in \{1, 2, \ldots, n\}에 대해 다음 두 조건을 만족하는 길이 nn의 순열 pp를 구해야 한다.

  • 위치 ii에서 끝나는 pp의 최장 증가 부분 수열의 길이는 aia_i와 같다.
  • 위치 ii에서 시작하는 pp의 최장 감소 부분 수열의 길이는 bib_i와 같다.

입력

첫째 줄에는 순열의 길이인 양의 정수 nn이 주어진다. (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)

둘째 줄에는 nn개의 정수 a1,a2,…,ana_1, a_2, \ldots, a_n이 주어진다. aia_i는 위치 ii에서 끝나는 최장 증가 부분 수열의 길이이다. (1≤ai≤n1 \le a_i \le n)

셋째 줄에는 nn개의 정수 b1,b2,…,bnb_1, b_2, \ldots, b_n이 주어진다. bib_i는 위치 ii에서 시작하는 최장 감소 부분 수열의 길이이다. (1≤bi≤n1 \le b_i \le n)

출력

원하는 순열 p1,p2,…,pnp_1, p_2, \ldots, p_n을 공백으로 구분해 한 줄에 출력한다.

답이 존재함이 보장된다. 답이 여러 개라면 아무거나 하나 출력해도 된다.

예제2

  1. 예제 1

    입력
    5
    1 1 1 2 3
    3 2 1 1 1
    
    예상 출력
    3 2 1 4 5
    
  2. 예제 2

    입력
    6
    1 1 2 2 3 3
    2 1 2 1 2 1
    
    예상 출력
    2 1 4 3 6 5