P10153 "LAOI-5" Mock Contest

LAOI members created a CSP-J mock contest with $10^{100}$ problems. 2025.1.24 The idea of this problem comes from [xzCyanBrad](/user/380730).

The contest uses the ICPC rules: first sort by the number of solved problems in non-increasing order, then sort by the total penalty time in non-decreasing order. There are $n$ top players coming to speedrun this contest, and the contest lasts $m$ minutes in total. At the beginning of minute $i$ ($0 \le i \le m-1$), player $s_i$ first submits $t_i$ WA submissions (each adds $x$ minutes of penalty), and then solves one problem. **So their solved count increases by $1$, and their total penalty time increases by $x \times t_i + i$ minutes.** Player $i$ has a total of $k_i$ WA submissions and solves $a_i$ problems (it is guaranteed that $\sum_{i=1}^n a_i = m$). Why did they not finish all problems? Because they thought the problems were too easy and not interesting, so they left. If player $i$ finds that they are in first place on the leaderboard (**no ties allowed**) after **finishing all of their submissions**, then we say they "speedrun the contest." Construct sequences $\{s_m\}$ and $\{t_m\}$ such that player $i$ has exactly $k_i$ WAs and solves exactly $a_i$ problems, and the number of players who "speedrun the contest" is as large as possible.

There are three lines in total. The first line contains three integers $n,m,x$. The second line contains $n$ integers, representing $\{a_n\}$. The third line contains $n$ integers, representing $\{k_n\}$.

Output the maximum number of players who "speedrun the contest" on the first line. On the second and third lines, output one optimal construction: The second line contains $m$ integers, representing $\{s_m\}$. The third line contains $m$ integers, representing $\{t_m\}$.

### Sample 1 Explanation At minute $2$, player $3$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 2 + 0 + 1 + 2 = 43$ minutes. At minute $5$, player $2$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 1 + 3 + 4 + 5 = 32$ minutes. At minute $8$, player $1$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 0 + 6 + 7 + 8 = 21$ minutes. ### Constraints **The testdata is not guaranteed to be random.** **This problem uses bundled tests.** |Subtask ID|Score|$n,m,x$| |:--:|:--:|:--:| |$1$|$10$|$n\le5$，$m \le50$，$x\le5$| |$2$|$10$|$n\le50$，$m\le500$| |$3$|$20$|$n\le10^3$，$m \le5\times10^3$| |$4$|$20$|$x=0$，$k_i=0$| |$5$|$40$|No special limits.| For $100\%$ of the testdata, it is guaranteed that: - $m\ge 3n$； - $3 \le n\le10^5$； - $9\le m\le 3\times10^5$； - $0\le x\le 5\times10^4$； - $0\le k_i \le 4\times10^4$； - $3\le\color{black} a_i \le 3\times10^5$； - $\sum ^{n}_{i=1} a_i = m$。 Translated by ChatGPT 5