Олимпиадный тренинг

Задача . F. Виталий и Advanced Useless Algorithms


Задача

Темы: дп жадные алгоритмы реализация *2200

Виталий записался на курс Advanced Useless Algorithms. Курс состоит из \(n\) заданий. Виталий подсчитал, что до задания \(i\) у него есть \(a_i\) часов на выполнение, начиная с дня записи на курс. То есть, дедлайн до задания \(i\) составляет \(a_i\) часов. Массив \(a\) отсортирован по возрастанию, другими словами, номера заданий соответствуют порядку сдачи заданий.

Виталий все делает добросовестно, поэтому он хочет выполнить каждое задание на \(100\) процентов, или больше. Изначально его уровень выполнения по каждому заданию равен \(0\) процентов.

У Виталия есть \(m\) опций подготовки, каждая опция может быть использована не более одного раза. Опция \(i\) характеризуется тремя целыми числами: \(e_i, t_i\) и \(p_i\). Если Виталий использует \(i\)-ю опцию, то через \(t_i\) часов (с текущего момента) он улучшит выполнение задания \(e_i\) на \(p_i\) процентов.

Например, пусть Виталию предстоит выполнить \(3\) задания. Пусть массив \(a\) имеет вид: \(a = [5, 7, 8]\). Допустим, Виталию доступны \(5\) опций: \([e_1=1, t_1=1, p_1=30]\), \([e_2=2, t_2=3, p_2=50]\), \([e_3=2, t_3=3, p_3=100]\), \([e_4=1, t_4=1, p_4=80]\), \([e_5=3, t_5=3, p_5=100]\).

Тогда если Виталий будет готовиться следующим образом, он сможет выполнить все вовремя:

  • Виталий выбирает опцию \(4\). Тогда через \(1\) час он выполнит задание \(1\) на \(80\) процентов. До дедлайна задания \(1\) ему остается ещё \(4\) часа.
  • Виталий выбирает опцию \(3\). Тогда через \(3\) часа он полностью выполнит задание \(2\). До дедлайна задания \(1\) у него остается ещё \(1\) час, а до дедлайна задания \(3\) ему остаётся \(4\) часа.
  • Виталий выбирает опцию \(1\). Тогда через \(1\) час он выполнит задание \(1\) на \(110\) процентов, то есть успеет выполнить задание \(1\) как раз к дедлайну.
  • Виталий выбирает опцию \(5\). Тогда \(2\) часа он будет выполнять задание \(3\), и через еще \(1\) час Виталий полностью выполнит задание \(3\).

Таким образом, Виталий полностью и вовремя сумел пройти курс, использовав \(4\) опции.

Помогите Виталию — выведите опции, по которым Виталию следует выполнить задания в нужном порядке. Обратите внимание: каждая опция может быть использована не более одного раза. Если существует несколько возможных ответов, разрешается вывести любой.

Входные данные

В первой строке входных данных записано целое число \(T\) (\(1 \le T \le 10^4\)) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора содержит два целых числа \(n\) и \(m\) (\(1 \le n,m \le 10^5\)) — количество заданий и количество опций подготовки соответственно.

В следующей строке заданы \(n\) чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) — время до дедлайна задания \(i\). Заданные значения — не убывают, то есть \(a_1 \le a_2 \le \dots \le a_n\).

Следующие \(m\) строк содержат тройки чисел \(e_i, t_i, p_i\) (\(1 \le e_i \le n\), \(1 \le t_i \le 10^9\), \(1 \le p_i \le 100\)) — если Виталий выберет эту опцию, то через \(t_i\) часов он улучшит выполнение задания с номером \(e_i\) на \(p_i\) процентов. Опции пронумерованы от \(1\) до \(m\) в порядке следования во входных данных.

Гарантируется, что сумма \(n+m\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите в первой строке число \(k\), означающие что за \(k\) опций Виталий сможет выполнить каждое задание на \(100\) процентов или больше вовремя. Опции не должны повторяться. Либо выведите -1, если Виталий не имеет возможности выполнить все задания вовремя.

Если ответ существует, то в следующей строке выведите \(k\) различных целых чисел от \(1\) до \(m\) — номера опций в нужном порядке. Если существует несколько ответов, разрешается вывести любой из них.


Примеры
№Входные данныеВыходные данные
1 5
3 5
5 7 8
1 1 30
2 3 50
2 3 100
1 1 80
3 3 100
1 5
51
1 36 91
1 8 40
1 42 83
1 3 45
1 13 40
2 9
9 20
2 8 64
2 7 64
1 20 56
2 8 76
2 20 48
1 2 89
1 3 38
2 18 66
1 7 51
3 2
7 18 33
1 5 80
3 4 37
2 5
569452312 703565975
1 928391659 66
1 915310 82
2 87017081 92
1 415310 54
2 567745964 82 
4
1 4 3 5 
3
2 4 5 
4
6 7 1 2 
-1
4
2 4 3 5
2 3
3 9
20 31 40
1 9 64
3 17 100
3 9 59
3 18 57
3 20 49
2 20 82
2 14 95
1 8 75
2 16 67
2 6
20 36
2 2 66
2 20 93
1 3 46
1 10 64
2 8 49
2 18 40
1 1
1000000000
1 1000000000 100 
-1
4
3 4 1 5 
1
1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет