#P3190. [JLOI2013]赛车

    ID: 2366 传统题 1000ms 512MiB 尝试: 2551 已通过: 628 难度: 6 上传者: 标签>难度分类提高计算几何直线上包络排序与序列处理单调栈自定义排序规则数值计算与优化有理数精确运算CF2000

[JLOI2013]赛车

[JLOI2013] 赛车

题目描述

有 nn 辆赛车在一条无限长的直线上比赛,编号为 11 到 nn。第 ii 辆车在比赛开始时位于起跑线前 kik_i 个单位的位置,然后以每秒 viv_i 个单位的恒定速度向前行驶。比赛中可以超车,不需要考虑车辆相撞。

如果某辆车在比赛开始时或之后的某个时刻位于最前方,它就能获奖。多辆车并列在最前方时,它们都算领跑。求所有获奖赛车的编号。

输入格式

第一行包含一个正整数 nn(1≤n≤1041\le n\le 10^4),表示赛车数。

第二行包含 nn 个整数 k1,…,knk_1,\ldots,k_n(0≤ki≤1090\le k_i\le 10^9),表示各车的起始位置。

第三行包含 nn 个整数 v1,…,vnv_1,\ldots,v_n(0≤vi≤1090\le v_i\le 10^9),表示各车的速度。

输出格式

第一行输出获奖赛车的数量。

第二行按编号递增的顺序输出获奖赛车的编号,编号之间用一个空格分隔。

4
1 1 0 0
15 16 10 20
3
1 2 4