#CW51. Petya 与邮局(petrol)

Petya 与邮局(petrol)

题目描述

有 nn 个首尾相接的邮局。邮局 ii 的加油站最多提供 aia_i 单位燃料;邮局 ii 和邮局 i+1i + 1 之间的双向路径需要消耗 bib_i 单位燃料,其中 bnb_n 对应从第 nn 个邮局和第 11 个邮局之间需要花费的燃料。

你可以选择任意邮局出发,初始燃料为 00,并选择一个方向后始终沿该方向行驶一整圈。行驶过程中燃料不能为负。请输出可以完成一整圈的出发邮局编号。

输入格式

从 petrol.in 文件读入数据。

第一行输入整数 nn。第二行输入 nn 个正整数 aia_i,第三行输入 nn 个正整数 bib_i。

输出格式

将结果输出到 petrol.out 文件。

第一行输出可行出发邮局的数量 rr。第二行按升序输出这 rr 个编号;若 r=0r = 0,第二行可以为空。

样例 1 输入

4
1 7 2 3
8 1 1 3

样例 1 输出

2
2 4

样例 2 输入

8
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1

样例 2 输出

8
1 2 3 4 5 6 7 8

数据范围

保证 1≤n≤1051 \le n \le 10^5,∑i=1nai≤109\sum_{i=1}^{n} a_i \le 10^9,∑i=1nbi≤109\sum_{i=1}^{n} b_i \le 10^9。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼41\sim 4 n≤100n \le 100
2 20 5∼85\sim 8 n≤2000n \le 2000
3 30 9∼149\sim 14 n≤50000n \le 50000
4 40 15∼2015\sim 20 n≤105n \le 10^5