시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 53 | 20 | 10 | 30.303% |
직선 형태의 강에 N+1개의 댐이 있다. 가장 왼쪽 댐의 왼쪽과 가장 오른쪽 댐의 오른쪽으로는 강이 더 이상 이어지지 않기에, 댐으로 인해 강은 길이가 같은 N개의 구간으로 나뉘어져 있다. 각 구간에서 강의 수위는 서로 다를 수 있다.
지나친 수질오염으로 인해 당신은 N+1개의 댐 중 몇 개를 파괴하기로 결정했다. 적어도 한 개의 댐을 파괴하여야 하며, 당연하지만 양쪽 끝에 있는 댐은 파괴할 수 없다.
댐을 파괴하고 나면 댐 양옆에 있던 물의 수위가 같아지도록 물이 이동할 것이다. 예를 들어 N=5이고 최초에 강의 수위가 다음과 같은 수열로 표현되었다고 하자.
2 5 2 6 9
이 상태에서 두 번째, 세 번째, 다섯 번째 댐을 파괴한다면 강의 수위는 다음과 같게 변한다.
3 3 3 7.5 7.5
그러나 몇몇 댐을 파괴함으로 인해 강의 수위가 급격하게 바뀐다면 다른 댐들도 균형을 잃고 무너질 수 있다.
N+1개의 댐에 대해 댐이 견딜 수 있는 강의 수위의 범위가 주어진다. 만약 어떤 댐의 왼쪽 혹은 오른쪽에 오는 강의 구간의 수위가 그 댐이 견딜 수 있는 수위의 범위를 벗아난다면 그 댐은 무너질 것이다. 초기 상태에서는 모든 댐이 무너지지 않는 상태임이 보장된다.
양쪽 끝에 있는 댐을 제외한 적어도 한 개의 댐을 파괴하고 나서, 다른 댐은 무너지지 않게 하는 방법을 제시하여라.
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 300,000)
두 번째 줄에는 댐으로 인해 나뉘어진 N개의 구간에서 강의 수위를 나타내는 수열 A가 주어진다. (1 ≤ Ai ≤ 7,777,777)
그 뒤로 N+1개의 줄에는 각 댐의 정보가 주어진다. i번째 댐의 정보는 두 정수 li과 ui로 표현되며 이는 그 댐이 견딜 수 있는 강의 수위가 li이상 ui이하임을 뜻한다. (1 ≤ li ≤ ui ≤ 7,777,777)
자연수 i (1 ≤ i ≤ N)에 대해 li ≤ hi ≤ ui 이며 li+1 ≤ hi ≤ ui+1 이다.
첫째 줄에 파괴할 댐의 수 K를 출력한다. (1 ≤ K ≤ N - 1)
둘째 줄에 파괴할 댐의 번호 K개를 공백으로 구분하여 출력한다. 댐의 인덱스는 0부터 시작한다. 따라서 당신이 출력해야 할 댐의 번호는 1 이상 N-1 이하이다. 댐의 번호는 모두 서로 달라야 한다.
만약 조건을 만족하도록 댐을 파괴하는 방법이 존재하지 않는다면 첫째 줄에 -1을 출력하여라.
5 2 5 2 6 9 2 4 2 5 2 5 2 8 6 9 6 9
3 1 2 4
5 4 5 9 4 5 4 4 4 6 4 10 4 10 4 5 5 5
-1
High School > 서울과학고등학교 > 2020 SciOI #1 D번