직각삼각형을 만들어요

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

요약
각 막대마다 천을 왼쪽이나 오른쪽으로 치는 방향을 정해 어떤 막대나 천도 서로 교차하지 않게 배치하고, 불가능하면 -1을 출력한다.
난이도

어려움10점 중 8점

유형
그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

캠핑장에 놀러 온 NN명의 호반우들은 직각삼각형 텐트를 만들기 위한 막대와 천을 하나씩 가지고 있다. 캠핑장의 땅은 수직선으로 표현할 수 있으며 ii번 호반우는 수직선 위의 a_ia\_{i} 지점에 길이 b_ib\_{i}의 막대를 세워 놓았다.

호반우들은 막대의 왼쪽이나 오른쪽에 위치한 수직선 위의 a_i±M⋅b_ia\_{i} \pm M \cdot b\_{i} 지점에서 막대의 꼭대기로 천을 일직선으로 이어 텐트를 완성할 건데 천이 다른 텐트의 막대나 천과 겹치거나 교차하면 안 된다. 천의 끝점에서 만나는 것도 교차하는 것으로 생각하며 막대와 천의 두께는 무시한다.

M=1M = 1일 때 가능한 텐트 배치의 예시이다.

M=1M = 1일 때 불가능한 텐트 배치의 예시이다.

텐트를 만들기 위해 천을 막대의 왼쪽과 오른쪽 중 어느 방향으로 쳐야 할지 고민에 빠진 호반우들을 도와주자.

입력

첫째 줄에 양의 정수 NN과 MM이 공백을 두고 주어진다. (1≤N≤300,000;1≤M≤109)(1 \leq N \leq 300\\,000 ; 1 \leq M \leq 10^{9})

둘째 줄에 막대의 위치인 양의 정수 a_1,a_2,a_3,⋯ ,a_Na\_{1}, a\_{2}, a\_{3}, \cdots, a\_{N}이 공백을 두고 주어진다. (1≤a_i≤109;a_i<a_i+1)(1 \leq a\_{i} \leq 10^{9};a\_{i} < a\_{i+1})

셋째 줄에 막대의 길이인 양의 정수 b_1,b_2,b_3,⋯ ,b_Nb\_{1}, b\_{2}, b\_{3}, \cdots, b\_{N}이 공백을 두고 주어진다. (1≤b_i≤109)(1 \leq b\_{i} \leq 10^{9})

출력

만약 NN개의 텐트를 만들 수 없다면 첫째 줄에 -1을 출력한다.

그렇지 않다면 첫째 줄에 L과 R로 이루어진 길이가 NN인 문자열을 출력한다. 문자열의 ii번째 문자가 L이라면 ii번 호반우가 막대의 왼쪽으로 R이라면 막대의 오른쪽으로 천을 이은 것을 의미한다.

가능한 방법이 여러 가지라면 그중 아무거나 출력한다.

예제3

  1. 예제 1

    입력
    4 1
    2 3 6 9
    1 2 6 4
    
    예상 출력
    LRLR
    
  2. 예제 2

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

    입력
    5 2
    1 2 4 7 9
    3 2 4 5 1
    
    예상 출력
    -1