Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
Statistics
【题目背景】

你正在机房里研究非对称排列组合游戏,这时候教练进来了,于是你赶紧开始做这道排列题。

【题目描述】

给定两个序列 $a_1,a_2,\dots ,a_n$ 和 $b_1,b_2, \dots ,b_n$。

求一个 $1,2,\dots ,n$ 的排列 ${c_n}$,使得 $\sum_{i = 1}^{n}\lceil \frac{\max(b_i - a_{c_i},0)}{k}\rceil$ 最小。

你需要输出方案。

【输入格式】

从文件 card.in 中读入数据。

第一行正整数两个数 $n, k$。

第二行 $n$ 个正整数 $a_1,a_2,\dots ,a_n$。

第三行 $n$ 个正整数 $b_1,b_2, \dots ,b_n$。

【输出格式】

输出到文件 card.out 中。

第一行一个整数表示答案。

第二行 $n$ 个数 $c_1,c_2, \dots ,c_n$。

如果有多组解,给出任意一组即可。

【样例 1 输入】
4 2
2 7 6 4
3 9 1 8
【样例 1 输出】
2
4 2 1 3
【测试点约束】

对于所有数据,保证 $1 \leq n \leq 10^5, 1 \leq a_i,b_i,k \leq 10^9$。

  • 子任务 1(10 分):$n \leq 10$。
  • 子任务 2(10 分):$n \leq 20$。
  • 子任务 3(30 分):$n \leq 500, k \leq 2000$。
  • 子任务 4(50 分):无特殊限制。