A34866.训练大计
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
时间限制:1S
空间限制:256MB
随着新的学期开始算法社又要开始招生了,算法社思来想去决定以看各位想入算法社同学的 Codesforces 网站中的竞赛分数,以分数越高者优先的方式进行第一轮选拔。
现总共有 n 名编号1~n同学选择加入算法社,而第一轮选拔算法社决定至少让 m 名同学晋级,并且这些同学竞赛分都不能低于 k 分,现在兴科手上有这 n 名同学的资料,资料中记录着同学们的起始分数以及潜力值;不过刚开始这些同学可能并不能达到算法社的招生需求,所以算法社将带领这 n 名同学进行一段时间的训练,每天每名同学的竞赛分都会提升潜力值的分值。现如今算法社对兴科施压要求兴科算出最快多少天会有至少 m 名同学晋级,和这一天到来时实际的晋级人数 x , 以及晋级同学的编号,兴科实在不知道怎么算,现在他找到了你请求你告诉他结果。
输入格式
在第一行上输入三个正整数 n,m,k (1≤m≤n≤2×105,0≤k≤1×109),n 表示同学数目, m 为最小的选拔人数,k 为最小分数要求。
第二行给出 n 个正整数 ai 表示第 i 位同学的初始分数,第三行给出 n 个正整数 bi 表示第 i 位同学的潜力值;(0≤ai≤1×109,1≤bi≤1×109 )
输出格式
第一行输出一个数代表需要训练的最少天数,第二行输出一个数 x 表示算法社第一轮实际入选的人数,第三行对 x 个晋级同学的最终竞赛分由大到小(如果竞赛分相同编号小优先)输出 x 个数表示晋级同学的编号。
输入输出样例
输入#1
5 3 8 1 2 3 8 10 3 1 2 1 5
输出#1
3 4 5 4 1 3
说明/提示
对于 30% 的数据, 1≤m≤n≤3000 。
对于 100% 的数据,1≤m≤n≤2×105,0≤k≤1×109,0≤ai≤1×109,1≤bi≤1×109 。