比赛 果蝇王邀请赛div2 评测结果 ATTTTTTTTT
题目名称 果蝇炸弹 最终得分 10
用户昵称 yanglich 运行时间 9.966 s
代码语言 C++ 内存使用 48.38 MiB
提交时间 2026-08-27 11:55:50
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int c,n,a[300005],r[300005];
long long ans;
bool vis[300005],t[300005];
map<string,bool>p;
void solve(int u){
    for(int i=u+1;i<=n;i++){
        if(a[u]+r[u]<a[i])break;
        if(!t[i]){
            t[i]=1;
            solve(i);
        }
    }
    for(int i=u-1;i>=1;i--){
        if(a[u]-r[u]>a[i])break;
        if(!t[i]){
            t[i]=1;
            solve(i);
        }
    }
}
void dfs(int x){
    if(x==n+1){
        for(int i=1;i<=n;i++){
            t[i]=vis[i];
            //cout<<t[i];
        }
        //cout<<"\n";
        for(int i=1;i<=n;i++){
            if(t[i])solve(i);
        }
        string s="";
        for(int i=1;i<=n;i++){
            s+=(t[i]+'0');
        }
        //cout<<s<<"\n";
        if(!p[s]){
            p[s]=1;
            ans++;
            ans%=(long long)(1e9+7);
        }
        return;
    }
    dfs(x+1);
    vis[x]=1;
    dfs(x+1);
    vis[x]=0;
}
signed main(){
    freopen("bombmine.in","r",stdin);
    freopen("bombmine.out","w",stdout);
    cin>>c>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>r[i];
//    t[4]=1;
//    solve(4);
//    for(int i=1;i<=n;i++)cout<<t[i];
    dfs(1);
    cout<<ans;
    return 0;
}