A34866.训练大计

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

时间限制:1S
空间限制:256MB

随着新的学期开始算法社又要开始招生了,算法社思来想去决定以看各位想入算法社同学的 CodesforcesCodesforces 网站中的竞赛分数,以分数越高者优先的方式进行第一轮选拔。
现总共有 nn 名编号11~nn同学选择加入算法社,而第一轮选拔算法社决定至少让 mm 名同学晋级,并且这些同学竞赛分都不能低于 kk 分,现在兴科手上有这 nn 名同学的资料,资料中记录着同学们的起始分数以及潜力值;不过刚开始这些同学可能并不能达到算法社的招生需求,所以算法社将带领这 nn 名同学进行一段时间的训练,每天每名同学的竞赛分都会提升潜力值的分值。现如今算法社对兴科施压要求兴科算出最快多少天会有至少 mm 名同学晋级,和这一天到来时实际的晋级人数 xx , 以及晋级同学的编号,兴科实在不知道怎么算,现在他找到了你请求你告诉他结果。

输入格式

在第一行上输入三个正整数 n,m,kn,m,k (1mn2×105,0k1×1091 \le m \le n \le 2 \times 10^5,0 \le k \le 1 \times 10^9),nn 表示同学数目, mm 为最小的选拔人数,kk 为最小分数要求。

第二行给出 nn 个正整数 aia_i 表示第 ii 位同学的初始分数,第三行给出 nn 个正整数 bib_i 表示第 ii 位同学的潜力值;(0ai1×109,1bi1×1090 \le a_i \le 1 \times 10^9,1 \le b_i \le 1 \times 10^9

输出格式

第一行输出一个数代表需要训练的最少天数,第二行输出一个数 xx 表示算法社第一轮实际入选的人数,第三行对 xx 个晋级同学的最终竞赛分由大到小(如果竞赛分相同编号小优先)输出 xx 个数表示晋级同学的编号。

输入输出样例

  • 输入#1

    5 3 8
    1 2 3 8 10
    3 1 2 1 5

    输出#1

    3
    4
    5 4 1 3

说明/提示

对于 30%30 \% 的数据, 1mn30001 \le m \le n \le 3000

对于 100%100 \% 的数据,1mn2×105,0k1×109,0ai1×109,1bi1×1091 \le m \le n \le 2 \times 10^5,0 \le k \le 1 \times 10^9,0 \le a_i \le 1 \times 10^9,1 \le b_i \le 1 \times 10^9

首页