进击蚂蚁
题目描述
有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在 t 秒后的位置和朝向。
输入格式
第一行，两个空格隔开的整数 n,t（代表蚂蚁数 n 和时间 t）。
第 2∼n+1 行每行两个整数，第 i+1 行代表第 i 只蚂蚁的初始位置 ai 及初始朝向 bi（bi=1 时蚂蚁朝右，bi=−1 时蚂蚁朝左）。
输出格式
共 n 行，每行两个整数，第 i 行代表 t 秒后第 i 只蚂蚁的位置及朝向（−1 表示朝左，1 表示朝右，0 表示正在转向中）。
输入输出样例 #1
输入 #1
4 1
1 1
5 1
3 -1
10 1
输出 #1
2 0
6 1
2 0
11 1
说明/提示
数据范围及约定
- 对于 40% 的数据，1≤n≤100；
- 对于 80% 的数据，1≤n≤104，0≤t≤1000；
- 对于 100% 的数据，n≤105，0≤t≤105，∣ai∣≤106。ai各不相同
| 测试点编号 |
n,t范围 |
ai分布 |
bi分布 |
| 1∼2 |
n≤100,t≤100 |
随机小范围(−103,103) |
相向而行(各占50%) |
| 3∼4 |
n≤100,t=0 |
随机分布 |
随机方向(1/-1) |
| 5∼6 |
n≤104,t≤1000 |
严格递增序列 |
全部朝右(1) |
| 7∼8 |
严格递减序列 |
全部朝左(-1) |
| 9∼10 |
n=1,t≤105 |
单个随机值 |
任意方向 |
| 11∼12 |
n≤105,t≤105 |
随机大范围(−106,106) |
全部同向(1或-1) |
| 13∼14 |
密集分布(差值=1) |
交替方向(1,-1,1...) |
| 15∼16 |
极端值(−106,106) |
相向而行(各占50%) |
| 17∼18 |
n=105,t=105 |
随机分布 |
随机方向 |
| 19∼20 |
对称排列(如±1,±2,...) |
对称相向 |
