P7610 [THUPC 2021] Stellar Connect

As everyone knows, Stellar and Princess Connect had a crossover! The result of the crossover is a game called Stellar Connect. This is a two-player, turn-based competitive game. The two players are Alice and Bob. The game consists of several **rounds**. In each round, the first player and the second player each take one action in order. Now, you have written an excellent AI to play this game. This AI follows the game rules and plays according to the fixed strategy described in the Game Process section. However, since you are too strong, there is only one such AI in the world, so it can only play against itself. Given the initial game state, let this AI play as Alice and Bob, with Alice moving first. You need to simulate the game process and determine whether Alice wins or Bob wins. The initial game state will be given in the input. **【Hint】** In this problem, **damage**, **true damage**, and **HP deduction** are three different concepts. Please be careful to distinguish them.

#### Basic Parameters First, before the game starts, each player must choose exactly $n$ characters and number them $1,2,3,\dots,n$. Each character has some basic parameters: 1. $HP,hp$：maximum HP, current HP； 2. $MP,mp$：maximum energy, current energy； 3. $atk,\Delta_{atk}$：base attack, attack bonus； 4. $def,\Delta_{def}$：base defense, defense bonus； In addition, for convenience, let $A=\max(atk+\Delta_{atk},1)$ and $D=\max(def+\Delta_{def},0)$. At the start of the game, current HP $hp$ equals maximum HP $HP$, and current energy $mp$, attack bonus $\Delta_{atk}$, and defense bonus $\Delta_{def}$ are all $0$. $HP,MP,atk,def$ are given in the input. Besides, each character has one **talent** and one **skill**, described in the **Talent** section and the **Skill** section. #### Death Check At any time during the game, if a character’s current HP $hp$ drops to $0$ or below, then that character is considered **dead**. Once a character is considered **dead**, it completely leaves the battlefield. Its HP is fixed at $0$, and it cannot regain HP in any way (i.e. it cannot be revived, even if it has **Talent — Mind Over Matter**; also, it cannot be healed by skills from other allies). It cannot perform normal attacks or cast skills, and it cannot be selected as a priority target, so it cannot be hit by normal attacks either. In short, it does not participate in the rest of the game in any form. In this problem, all phrases like “all”, “all characters”, etc. do not include **dead** characters. When all characters on one side are considered **dead**, the game ends immediately and the other side wins (if there are still unresolved effects at this moment, none of them will be processed). #### Parameter Overflow At any time during the game, if a character has $hp>HP$, then $hp$ immediately becomes $HP$. At any time during the game, if a character has $mp>MP$, then $mp$ immediately becomes $MP$. #### Priority Target Before the game starts, each player must specify an attack order for each character. Specifically, for character $i$, you must determine an attack order $p_{i,1},\ldots,p_{i,n}$, where $p_{i,1},\ldots,p_{i,n}$ is a permutation of $1,\ldots,n$. At any time during the game, the priority target of character $i$ is $p_{i,j}$ if and only if $p_{i,1},\ldots,p_{i,j-1}$ are all **dead**, and $p_{i,j}$ is not **dead**. #### Normal Attack A normal attack deals $A$ damage to the priority target. A character with **Talent — Transcendence** will instead deal $A$ true damage to the priority target. See the **Talent** section. A character with **Talent — Stellar Power Projection** will add true damage to its normal attack. See the **Talent** section. #### Talent Talents have the following types (the number at the start of each line is the talent type ID, and the parentheses `()` contain extra parameters): 0. **Talent — I Shut Down**: This character’s talent has no effect； 1. **Talent — Flesh and Blood**: This character is immune to half of true damage. See the **HP Deduction Phase** section for details. **True damage is described in the HP Deduction section**； 2. **Talent — Stellar Power Projection** $(x)$: Each normal attack by this character additionally deals $x$ true damage； 3. **Talent — Mind Over Matter** $(x,y)$: After each allied action ends, this character restores $x$ HP and **additionally** restores $y$ energy； 4. **Talent — Transcendence**: This character’s normal attack is treated as a true-damage attack; i.e. its normal attack deals no damage, but deals $A$ true damage； 5. **Talent — Technology Above All** $(x,y)$: After each normal attack, this character restores $x$ HP; after each skill cast, this character **additionally** restores $y$ energy. Note: if the normal attack or skill cast causes all enemy characters to become **dead**, then this character will no longer restore HP or energy. This problem guarantees that all extra talent parameters are **positive** integers (but they may be $0$ in the input; see the **Input Format** section for details). #### Skill When a character’s energy equals its maximum energy (and the character is selected to cast a skill during the game), it may clear its energy to $0$ and cast one skill. Skills have the following types (the number at the start of each line is the skill type ID, and the parentheses `()` contain extra parameters): 0. **Skill: Mind Broken!** This character’s active skill has no effect. Note: the skill can still be cast, it just has no effect. 1. **Skill: Green Explosion!** $(x)$ Deal $x$ damage to **all** enemy characters, **then** reduce the energy of **all** enemy characters by $\left\lfloor\frac{mp_{enemy}}{10}\right\rfloor$, where $mp_{enemy}$ is that enemy character’s current energy (i.e. for each enemy character, if its current energy is $mp_{enemy}$, then after this skill it becomes $mp_{enemy}-\left\lfloor\frac{mp_{enemy}}{10}\right\rfloor$). Note: by the rules, enemy characters first take damage and enter the HP Deduction Phase, restoring energy in that phase, and only then have their energy reduced by this skill. 2. **Skill: Sun (zhou) Rise (ji) (dao) Rain (dan)!** Deal $A$ true damage to **all** enemy characters. 3. **Skill: Heavenly Tower Overlord Severing Sword!** $(x)$ Deal $\min\left(\left\lfloor\frac{HP_{enemy}}{10}\right\rfloor,x\times A\right)$ damage to **all** enemy targets, where $HP_{enemy}$ is the target’s maximum HP. 4. **Skill: The Show Begins!** $(x,y)$ Let the current round be round $t$. From the moment this skill is cast until the end of round $t+x-1$, at the end of each allied action, all allied characters **additionally** restore $y$ energy. 5. **Skill: Heavenly Wolf Devouring Slash!** $(x)$ Decrease the priority target’s defense bonus by $x$, **then** deal $A$ true damage to the priority target. 6. **Skill: Earth (Too) Blue (Void) Azure (Blue) Flash (Flash) Lightning!** $(x,y)$ Deal $A$ true damage to the priority target. Also, let the current round be round $t$. From the moment this skill is cast until the end of round $t+x-1$, decrease all enemy characters’ attack bonus by $y$. 7. **Skill: Aurora Bloom!** $(x,y,z)$ Make exactly one allied character (not **dead**) with the lowest current HP (if multiple, choose the smallest index) restore $z$ HP. Also, let the current round be round $t$. From the moment this skill is cast until the end of round $t+x-1$, increase all allied characters’ attack bonus by $y$. 8. **Skill: Meteor!** $(x,y)$ Deal $A$ damage to all enemy characters. Let the current round be round $t$. **After this skill deals damage**, until the end of round $t+x-1$, decrease all enemy characters’ defense bonus by $y$. Note: this skill deals damage first, then applies the debuff. 9. **Skill: Elf’s Blessing!** $(x,y,z)$ All allied characters restore $z$ HP. Let the current round be round $t$. From the moment this skill is cast until the end of round $t+x-1$, increase all allied characters’ defense bonus by $y$. 10. **Skill: Full Power Ultra Full Burst! The End of Samsara!** $(x)$ All allied characters’ base attack $atk$ and base defense $def$ become twice their original values, i.e. $2\times atk, 2\times def$; for characters not **dead**, current HP $hp$ becomes $\max\left(\left\lfloor\frac{HP}2\right\rfloor,hp\right)$, and current energy $mp$ becomes $\max\left(\left\lfloor\frac{MP}2\right\rfloor,mp\right)$; let the current round be round $t$. From the moment this skill is cast until the end of round $t+x-1$, at the end of each allied action, all allied characters **additionally** restore $1$ energy. At the end of round $t+x-1$, if the enemy still has any character not **dead**, then all allied characters are forced to have their HP cleared to $0$ and are considered **dead**. In addition, when this skill is cast, all characters on the field that have this skill (including itself) will have their skill forcibly replaced with skill ID $0$, **Skill: Mind Broken!** (therefore this skill can be cast at most once in the game). This problem guarantees that all extra skill parameters are **positive** integers (but they may be $0$ in the input; see the **Input** section for details). Note: effects of the form “let the current round be $t$, then from casting this skill until the end of round $t+x-1$, …” **can stack**. #### HP Recovery and Energy Recovery HP can only be restored through talents and skills. At the end of each allied action, all allied characters gain $1$ energy. Characters with **Talent — Mind Over Matter**, and characters affected by **Skill: The Show Begins!** and **Skill: Full Power Ultra Full Burst! The End of Samsara!**, can gain extra energy. After an allied character performs a normal attack or casts a skill, that character gains $1$ energy. Characters with **Talent — Technology Above All** gain extra energy after casting a skill. Note: when casting a skill, first clear all energy, then cast the skill, then increase energy. In particular, if the skill is **Skill: Full Power Ultra Full Burst! The End of Samsara!**, then after setting the caster’s $mp=\max\left(mp,\left\lfloor\frac{MP}2\right\rfloor\right)$, increase energy. When an allied character enters the HP Deduction Phase due to taking damage, that character gains $1$ energy (regardless of whether it actually loses HP). **HP deduction is described in the HP Deduction Phase section.** #### HP Deduction Phase When a character takes damage or true damage, it immediately enters the HP Deduction Phase (note that even if it takes $0$ damage, it still enters the HP Deduction Phase). After entering the HP Deduction Phase, according to the energy recovery rules, its energy increases by $1$. Suppose it takes $x$ damage and $y$ true damage, then: - If it is immune to half of true damage due to **Talent — Flesh and Blood**, then its HP is reduced by $\max(x-D,0)+y-\left\lfloor\frac y2\right\rfloor$. - Otherwise, its HP is reduced by $\max(x-D,0)+y$. #### Game Process After the game starts, it can be viewed as several rounds, numbered starting from $1$. Each round can be divided into the following $5$ phases: Alice’s action (during), end of Alice’s action, Bob’s action (during), end of Bob’s action, end of the current round. During an allied action, 1. If there exists at least one allied character that can cast a skill, then choose one to cast a skill in decreasing order of skill ID. If multiple characters can cast the same highest-ID skill, choose the character with the largest character index among them to cast the skill. 2. If no allied character can cast a skill, then choose one character whose priority target currently has the highest HP to perform a normal attack. If multiple characters have priority targets with the highest HP, choose the character that would deduct more HP from its priority target (not the one that would deal more damage). If there are still multiple choices, choose the one with the largest character index to perform a normal attack. Then the allied action ends. Note: during an allied action, you can only choose one character to cast a skill, or choose one character to perform a normal attack.

The first line contains a positive integer $n$, meaning Alice and Bob each have $n$ characters. The next $4n$ lines describe Alice’s character $i$ from line $4i-3$ to line $4i$. In these four lines: - Line 1: four non-negative integers $HP,MP,atk,def$, representing the character’s maximum HP, maximum energy, base attack, and base defense, with $HP,MP>0$ guaranteed. - Line 2: $n$ positive integers $p_{i,1},p_{i,2}, \ldots ,p_{i,n}$, representing the character’s attack order, guaranteed to be a permutation of $1$ to $n$. - Line 3: three non-negative integers $tf,x,y$, representing the talent ID and extra parameters. If this talent has fewer than two extra parameters, you may ignore the extra parts (it is guaranteed that these extra parts are $0$ in the input). - Line 4: four non-negative integers $jn,x,y,z$, representing the skill ID and extra parameters. If this skill has fewer than three extra parameters, you may ignore the extra parts (it is guaranteed that these extra parts are $0$ in the input). The next $4n$ lines describe Bob’s $n$ characters in the same format.

If the game can end with one side winning, then: - Line 1: output a positive integer $x$, meaning the game ends in round $x$. - Line 2: output a string (`Alice` or `Bob`) indicating the winner. - Line 3: output $n$ non-negative integers, in order, representing each of the winner’s characters’ $hp$ at the end of the game; output $0$ if the character is dead. If the game will never end or the two sides draw, output any cute emoticon.

**【Constraints】** $n \le 10$, $HP, MP, atk \gt 0$, $def \ge 0$. It is guaranteed that at any time during the game, the absolute value of every parameter and expression mentioned in the statement does not exceed ${10}^9$. It is guaranteed that the game ends within $23333$ rounds. **【Source】** From the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021). Resources such as editorials can be found at [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master). Translated by ChatGPT 5