Задача №114483. Комбокамень
дна большая компания разрабатывает компьютерную игру «Комбокамень», которая должна мигом перевернуть всю индустрию. Правила игры достаточно сложные, и на реализацию серверного движка, моделирующего ход игры, был объявлен конкурс. От вас требуется реализовать подобный серверный движок.
Суть игры — игроки умеют призывать на арену и усиливать существ, используя заклинания, а также заставлять их сражаться друг с другом. Каждое существо имеет два параметра — численное значение атаки \(a\) и численное значение оставшегося здоровья \(h\). Для краткости будем обозначать параметры существа как \((a, h)\). Исходно на арене нет существ.
Игроку доступны следующие заклинания:
- Призыв существа : Призвать новое существо с характеристиками \((1, 1)\). Если уже в игру было введено \(k\) существ, то новое существо получает номер \(k+1\).
- Благословение силы : Удвоить атаку выбранного существа. Если до применения этого заклинания оно имело характеристики \((a, h)\), то после этого действия оно будет иметь характеристики \((2a, h)\).
- Божественный дух : Удвоить здоровье выбранного существа. Если до применения этого заклинания оно имело характеристики \((a, h)\), то после этого действия оно будет иметь характеристики \((a, 2h)\).
- Копия из лавы : Призвать новое существо, которое будет иметь такие же характеристики, как и выбранное заклинанием существо. Если уже в игру было введено \(k\) существ, то новое существо получает номер \(k+1\).
- Сражайся! : Заставить двух различных существ сразиться. Во время сражения оба существа одновременно наносят друг другу по одному удару, уменьшая количество здоровья соперника на значение своей атаки. Так, если сражаются два существа с характеристиками \((a_1, h_1)\) и \((a_2, h_2)\), то после сражения они будут иметь характеристики \((a_1, h_1-a_2)\) и \((a_2, h_2-a_1)\), соответственно. Если после сражения у существа остается 0 или меньше единиц здоровья, оно умирает и больше не может участвовать в игре.
От серверного движка, на реализацию которого объявлен конкурс, требуется способность промоделировать все события и для каждого созданного во время игры существа вывести номер хода, на котором оно погибло, либо определить, что оно осталось живо к концу игры.
Кроме того, движок должен корректно обрабатывать случаи, когда игрок пытается взаимодействовать с мертвыми по мнению сервера существами: если заклинание Благословение силы , Божественный дух или Сражайся! обращено к уже мертвому существу, то не должно произойти ничего. Если заклинание Копия из лавы применено к мертвому существу, создается его мертвая копия с такими же характеристиками, но умершая на текущем ходу, в момент копирования.
В первой строке дано число \(n\) — количество совершенных ходов (\(1 \le n \le 250\,000\)).
В следующих \(n\) строках даны ходы, пришедшие к серверному движку, в следующем формате:
- \(1\) — применить заклинание Призыв существа ;
- \(2\) \(i\) — применить заклинание Благословение силы к существу с номером \(i\);
- \(3\) \(i\) — применить заклинание Божественный дух к существу с номером \(i\);
- \(4\) \(i\) — применить заклинание Копия из лавы к существу с номером \(i\);
- \(5\) \(i\) \(j\) — применить заклинание Сражайся! к существам с номерами \(i\) и \(j\).
Гарантируется, что любые упомянутые в запросах существа к моменту запроса уже были призваны, но, возможно, могут уже быть мертвы.
В первой строке выведите одно целое число \(k\) — количество существ, призванных за время игры.
В следующей строке выведите \(k\) целых чисел \(t_1, t_2, \ldots, t_k\) — если существо с номером \(i\) осталось живо к концу игры, то \(t_i\) должно быть равно \(-1\), иначе \(t_i\) должно быть равно номеру хода, на котором оно погибло.
В таблице можно увидеть, как изменялись характеристики существ в первом примере.
|
ход |
1 | 2 | 3 | 4 | 5 |
|
0 |
- | - | - | - | - |
| 1 | (1, 1) | - | - | - | - |
| 2 | (2, 1) | - | - | - | - |
| 3 | (2, 2) | - | - | - | - |
| 4 | (2, 2) | (1, 1) | - | - | - |
| 5 | (2, 1) | мертво | - | - | - |
| 6 | (2, 2) | мертво | - | - | - |
| 7 | (2, 2) | мертво | (1, 1) | - | - |
| 8 | (2, 2) | мертво | (1, 2) | - | - |
| 9 | (2, 2) | мертво | (1, 4) | - | - |
| 10 | (2, 2) | мертво | (1, 4) | (2, 2) | - |
| 11 | (2, 1) | мертво | (1, 2) | (2, 2) | - |
| 12 | (2, 1) | мертво | (1, 4) | (2, 2) | - |
| 13 | мертво | мертво | (1, 2) | (2, 2) | - |
| 14 | мертво | мертво | мертво | (2, 1) | - |
| 15 | мертво | мертво | мертво | (2, 1) | - |
| 16 | мертво | мертво | мертво | (2, 1) | мертво |
16 1 2 1 3 1 1 5 1 2 3 1 1 3 3 3 3 4 1 5 1 3 3 3 5 1 3 5 4 3 5 4 3 4 1
5 13 5 14 -1 16