比赛 果蝇王邀请赛div2 评测结果 AWWWWWEEEE
题目名称 果蝇炸弹 最终得分 10
用户昵称 对立猫猫对立 运行时间 1.370 s
代码语言 C++ 内存使用 26.05 MiB
提交时间 2026-08-27 11:32:00
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define endl '\n'
using namespace std;
int c, n;
int a[5005], r[5005], ans;
vector<int> g[5005];
bool chk(int sit) {
    for(int j = 1; j <= n; j++) {
        if(sit & 1 << (j - 1)) {
            for(int p : g[j]) {
                if(!(sit & 1 << (p - 1))) {
                    return false;
                }
            }
        }
    }
    return true;
}
signed main() {
    freopen("bombmine.in", "r", stdin);
    freopen("bombmine.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> c;
    cin >> n;
    if(n > 30) {
        cout << "No!" << endl;
    }
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> r[i];
    }
    for(int i = 1; i <= n; i++) {
        int L = lower_bound(a + 1, a + n + 1, a[i] - r[i]) - a;
        int R = lower_bound(a + 1, a + n + 1, a[i] + r[i] + 1) - a;
        R--;
        if(L >= R) continue;
        else {
//            cout << i << " " << L << " " << R << endl;
            for(int j = L; j <= R; j++) {
                if(j != i) g[i].push_back(j);
            }
        }
    }
    for(int i = 0; i <= (1 << n) - 1; i++) {
        if(chk(i)) ans++;
        ans %= MOD;
    }
    cout << ans % MOD << endl;
    return 0;
}