题目描述

难度分:$1600$

输入$n(1 \leq n \leq 2 \times 10^5)$，表示某人参加了$n$场$CF$比赛。

然后输入$n$行，每行两个数$c(-100$~$100)$和$d(1$~$2)$，其中$c$表示比赛后这个人的$rating$变化了

$c$（正数表示上分，负数表示掉分，$0$表示不变），$d$表示这个人参加的是$div1$还是$div2$。

比赛前$rating \geq 1900$才能参加$div1$；比赛前$rating \leq 1899$才能参加$div2$。

输出$n$场比赛后，$rating$最大可以是多少。

如果$rating$可以无限大（见样例$3$），输出Infinity。

如果输入的数据自相矛盾（见样例$2$），输出Impossible。

输入样例$1$

3
-7 1
5 2
8 2

输出样例$1$

1907

输入样例$2$

2
57 1
22 2

输出样例$2$

Impossible

输入样例$3$

1
-5 1

输出样例$3$

Infinity

输入样例$4$

4
27 2
13 1
-50 1
8 2

输出样例$4$

1897

算法

二分答案

这个题看着就能用二分来做，首先我们很容易想到，由于$n$场变化对分数的变化是不会改变的，因此只需要初始分数最大就可以了。而竞赛分会受到如下约束：

1. 如果打到某场$div1$时，发现分数达不到$div1$的门槛，说明初始分数给低了。
2. 如果打到某场$div2$时，发现分数已经达到了$div1$的门槛，说明初始分数给高了。
3. 否则只要能顺利走完$n$场比赛，就说明初始分数是合适的，记录一下，然后往右搜索看能不能更大。

注意分数是可以为负数的，因此二分的上下界可以取$[-10^{12},10^{12}]$，如果求出来的答案特别大，说明分数可以无限大，输出Infinity。最后的答案还需要经过一次检查，看有没有自相矛盾的地方，有就要输出Impossible，否则输出求得的最大分数即可。

复杂度分析

时间复杂度

假设二分上下界的跨度为$A$，每次二分在$check$的时候就是遍历$n$次比赛的分数变化情况，时间复杂度为$O(n)$，因此算法整体的时间复杂度为$O(nlog_2A)$。

空间复杂度

除了输入的$n$次分数变化以及对应比赛的类别，在二分的过程中仅使用了有限几个变量，时间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, c, d;

int check(vector<PII>& tup, LL score) {
    for(int i = 0; i < n; i++) {
        if(tup[i].second == 1) {
            if(score < 1900) {
                return -1;     // 太低了
            }else {
                score += tup[i].first;
            }
        }else {
            if(score >= 1900) {
                return 1;      // 太高了
            }else {
                score += tup[i].first;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d", &n);
    vector<PII> tup;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &c, &d);
        tup.push_back({c, d});
    }
    LL l = -1e12, r = 1e12, ans = -1;
    while(l <= r) {
        LL mid = l + r >> 1;
        int t = check(tup, mid);
        if(t <= 0) {
            if(t == 0) {
                ans = mid;
            }
            l = mid + 1;
        }else {
            r = mid - 1;
        }
    }
    if(ans > (int)1e9) {
        puts("Infinity");
        exit(0);
    }
    for(int i = 0; i < n; i++) {
        if(tup[i].second == 1) {
            if(ans < 1900) {
                puts("Impossible");
                exit(0);
            }
        }else {
            if(ans >= 1900) {
                puts("Impossible");
                exit(0);
            }
        }
        ans += tup[i].first;
    }
    printf("%lld\n", ans);
    return 0;
}