아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

План защиты

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

요약
공격 세기와 한계 m이 주어질 때, m보다 큰 공격을 모두 덮는 길이 x의 겹치지 않는 구간을 최소 개수로 고르되 n-x+1번째 공격 뒤에는 떠나지 않도록 정한다.
난이도

보통10점 중 6점

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

문제

На'ви из племени Оматикайя предстоит защитить свой дом от nn нападений <<небесных людей>> на их Дерево-Дом, после которых планируется масштабная атака на Эйву.

Тсахик клана сообщает, что сила ii-й из планирующихся атак равна a_ia\_i. С прошлого раза воины племени много тренировались и могут спокойно отбить атаки силы не более mm, однако при любой атаке большей силы они понесут потери. Джейк не готов терять ни одного воина клана, поэтому во время атак, с которыми им не справиться, племя укрывается на островах у рифового клана Меткайина.

Меткайина не готовы укрывать у себя чужаков слишком долго, а дорога до них длинная, поэтому у них можно укрыться ровно на xx последовательных атак, не больше и не меньше. При этом, разумеется, сразу после последней атаки Оматикайя должны находиться дома, на своей территории, чтобы предотвратить последующую атаку на Эйву. Иными словами, нельзя покидать домашнюю территорию после n−x+1n - x + 1-й атаки, в таком случае племя не успеет вернуться назад.

Теперь Джейку необходимо спланировать план защиты или временного отступления так, чтобы не потерять ни одного члена клана. Помогите ему определить, возможно ли это, и если да, то какое минимальное число раз им придется просить убежище у Меткайина.

입력

В первой строке через пробел даны три целых числа nn, xx и mm --- количество атак, число атак подряд, которые можно переждать на островах, и максимальная сила атаки, которую Оматикайя могут отбить (1⩽x⩽n⩽5⋅1051 \leqslant x \leqslant n \leqslant 5 \cdot 10^5; 0⩽m⩽1090 \leqslant m \leqslant 10^9).

В следующей строке через пробел перечислены nn целых чисел a_ia\_i --- силы атак (0⩽a_i⩽1090 \leqslant a\_i \leqslant 10^9).

출력

Если такой план составить невозможно, выведите единственное число −1-1.

Иначе в первой строке выведите kk --- минимальное количество раз, которое придется укрыться всем племенем на островах, после чего во второй строке выведите kk целых чисел от 11 до nn --- номера атак, перед которыми племени стоит покидать Дом-Дерево и отправляться в сторону островов.

Если возможных ответов несколько, выведите любой из них.

예제2

  1. 예제 1

    입력
    3 2 0
    1 0 2
    
    예상 출력
    -1
    
  2. 예제 2

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