图解坠落的蚂蚁
https://blog.csdn.net/csyifanZhang/article/details/105726123
↑更好的阅读体验

思路分析

首先我们需要明确一点，

0次碰撞时，其速度本身就为0，2次碰撞是什么情况呢？

经过两次碰撞之后，A会再次装上右侧的速度为0的蚂蚁，他的速度又回到0，永远走不出去。

从上面图中我们可以看到，我们只考虑了A的左侧向右走的蚂蚁，和A的右侧向左走的蚂蚁，那么还有两类左侧向左走，右侧向右走，他们对A有影响吗？

考虑下面左图和右图，左图中A左侧有一个向左的蚂蚁和一个向右的蚂蚁，二者相碰时则交换速度，此时对A而言，相当于右图中我们只有一个向右的蚂蚁的场景，同理，右侧向右的蚂蚁对A也是没有影响的。这也就是为什么，我们可以将蚂蚁看作可以互相穿过，而不是碰撞掉头。

到这里，我们已经找到了蚂蚁不能坠落的条件，也知道了影响A的个体，因此我们可以使用两个数组分别存储A的左侧向右的蚂蚁和A的右侧向左的蚂蚁，然后再来讨论他们是如何影响A的结果的（以下都假设l,r包含蚂蚁的数目各不相等），我们不妨从最简单的情况开始推导：

上面三种情况基本上包含了所有的不想等的情况，我们依次来讨论一下

1. 对于第一种情况，显然A需要的时间是。
2. 对于第二种情况，在后面，而右侧不会将A变向，所以答案仍然是。
3. 对于第三种情况，A先和碰撞，再和碰撞，此时他的速度为0，因为我们看作蚂蚁可以互相穿过所以他最后总会和碰撞，因此答案是(还是画图吧)

我们发现右侧有两个，左侧有一个的时候，决定因素在于右侧的第二个，因为左右侧相同数目的蚂蚁互相抵消，他们的碰撞使得A的速度最终为0，而打破僵局的那个蚂蚁，就是第一个左右侧数目不对等的蚂蚁。（左3右4那就是右面第四个，左3右1那就是左面第二个）

struct P {
    ll pos, v;
}a[MAX];

bool cmp(P p1, P p2) { return p1.pos < p2.pos; }

int main() {
    ll n, s;
    while (cin >> n) {
        vector<P> vl, vr;
        for (int i = 0; i < n; i++) {
            cin >> a[i].pos >> a[i].v;
            if (a[i].v == 0)s = i;
        }
        for (int i = 0; i < n; i++) {
            if (a[i].pos < a[s].pos&&a[i].v>0)vl.push_back(a[i]);
            else if (a[i].pos > a[s].pos&&a[i].v < 0)vr.push_back(a[i]);
        }
        ll l1 = vl.size(), l2 = vr.size();
        sort(vl.begin(), vl.end(), cmp); sort(vr.begin(), vr.end(), cmp);
        if (l1 == l2)printf("Cannot fall!\n");
        else if (l1 > l2) 
            cout << 100 - vl[l1 - l2 - 1].pos << endl;//99还没掉下去
        else cout << vr[l1].pos << endl;
    }
}