P13538 [IOI 2025] 节日游戏（festival）
题目描述
节日上 Nayra 正在玩一个游戏，大奖是一次去红湖（Laguna Colorada）的旅行。游戏中玩家使用代币购买礼券。每购买一张礼券都有可能会获得额外的代币。游戏的目标是获得尽可能多的礼券。
开始时她有 $A$ 枚代币。游戏中一共有 $N$ 张礼券，从 $0$ 到 $N-1$ 编号。Nayra 需要支付 $P[i]$ 枚代币（$0 \leq i < N$）来购买礼券 $i$（购买前她至少要有 $P[i]$ 枚代币）。每张礼券最多只能购买一次。
此外，每张礼券 $i$（$0 \leq i < N$）都指定了**类型**，记为 $T[i]$，其值为 **$1$ 到 $4$ 之间**的整数。当 Nayra 购买礼券 $i$ 后，她剩余的代币数量将乘以 $T[i]$。形式化地，如果她在游戏的某个时刻有 $X$ 枚代币，并购买了礼券 $i$（要求 $X \geq P[i]$），那么购买后她将有 $(X - P[i]) \cdot T[i]$ 枚代币。
你的任务是确定 Nayra 应该购买哪些礼券以及按什么顺序来购买，使她最终拥有的**礼券**数量最大化。如果有多种购买序列能达成该目标，你可以回答其中任意一种。
### 实现细节
你要实现以下函数：
```
std::vector max_coupons(int A, std::vector P, std::vector T)
```
* $A$: Narya 初始拥有的代币数量。
* $P$: 长度为 $N$ 的数组，表示礼券的价格。
* $T$: 长度为 $N$ 的数组，表示礼券的类型。
* 对每个测试用例，该函数恰好被调用一次。
该函数应返回一个数组 $R$，按以下规则表示 Narya 的购买计划：
* 数组 $R$ 的长度应等于她最多可以购买的礼券数量。
* 数组中的元素为她购买的礼券编号，按购买的顺序排列。也就是说，她首先购买礼券 $R[0]$，然后购买礼券 $R[1]$，以此类推。
* $R$ 中所有的元素互不相同。
如果无法购买任何礼券，则 $R$ 应为空数组。
输入格式
输入格式：
```
N A
P[0] T[0]
P[1] T[1]
...
P[N-1] T[N-1]
```
输出格式
输出格式：
```
S
R[0] R[1] ... R[S-1]
```
其中，$S$ 是 `max_coupons` 返回的数组 $R$ 的长度。
说明/提示
### 例 1
考虑以下调用。
```
max_coupons(13, [4, 500, 8, 14], [1, 3, 3, 4])
```
Narya 起初有 $A = 13$ 枚代币。她可以按以下顺序购买 $3$ 张礼券：
| 购买的礼券 | 礼券价格| 礼券类型 | 购买后的代币数量 |
| :-----------: | :----------: | :---------: | :---------------------------------: |
| $2$ | $8$ | $3$ | $(13 - 8) \cdot 3 = 15$ |
| $3$ | $14$ | $4$ | $(15 - 14) \cdot 4 = 4$ |
| $0$ | $4$ | $1$ | $(4 - 4) \cdot 1 = 0$ |
在这个例子中，Narya 不可能购买多于 $3$ 张的礼券，并且上述购买顺序是她购买这 $3$ 张礼券的唯一方式。因此，该函数应返回 $[2, 3, 0]$。
### 例 2
考虑以下调用。
```
max_coupons(9, [6, 5], [2, 3])
```
在这个例子中，Narya 可以以任意顺序购买两张礼券。因此，该函数可以返回 $[0, 1]$ 或 $[1,0]$。
### 例 3
考虑以下调用。
```
max_coupons(1, [2, 5, 7], [4, 3, 1])
```
在这个例子中，Narya 有 $1$ 枚代币，不足以购买任何一张礼券。因此，该函数应返回 $[\ ]$ （空数组）。
### 约束条件
* $1 \leq N \leq 200\,000$
* $1 \leq A \leq 10^{9}$
* 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq P[i] \leq 10^{9}$。
* 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq T[i] \leq 4$。
### 子任务
| 子任务 | 分数 | 额外的约束条件 |
| :-----: | :---: | ------------------------------------------------------------------- |
| 1 | $5$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $T[i] = 1$。|
| 2 | $7$ | $N \leq 3000$；对每个满足 $0 \leq i < N$ 的 $i$，都有 $T[i] \leq 2$。|
| 3 | $12$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $T[i] \leq 2$。|
| 4 | $15$ | $N \leq 70$ |
| 5 | $27$ | Nayra 可以购买所有 $N$ 张礼券（以某种顺序）。|
| 6 | $16$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $(A - P[i]) \cdot T[i] < A$。|
| 7 | $18$ | 没有额外的约束条件。 |