#1197477 (C++17) No.3789 Binary 0-count Sequence

• 問題: No.3789 Binary 0-count Sequence
• ユーザー: Rubikun
• 提出日時: 2026-11-06 22:58:04
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2,025 ms / 3,000 ms
• コード長: 3,090 bytes
• コンパイル時間: 1,599 ms
• コンパイル使用メモリ: 220,416 KB
• 実行使用メモリ: 11,236 KB
• 最終ジャッジ日時: 2026-11-06 22:58:31
• 合計ジャッジ時間: 15,821 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

ファイルパターン	結果
sample	AC * 1
other	AC * 17

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=15LL<<58;

int f(ll x){
    if(x==0) return 1;
    ll a=__builtin_clzll(x);
    a=64-a;
    return a-__builtin_popcountll(x);
}

bool check(vi &S,ll st){
    for(int i=0;i<si(S);i++){
        if(f(st+i)!=S[i]) return false;
    }
    return true;
}

ll gutyoku(vi S){
    for(ll x=0;x<=1000;x++){
        if(check(S,x)) return x;
    }
    return -1;
}

ll esper(vi A){
    ll N=si(A);
    ll n=1;
    while(n<N) n*=2;
    n*=2;
    ll ans=INF;
    for(ll x=0;x<=n;x++){
        if(check(A,x)){
            ans=x;
            break;
        }
    }
    if(ans!=INF){
        return ans;
    }
    for(ll a=0;a<n;a++){
        ll now=a;
        for(ll t=n;t<=INF;t*=2){
            now+=t;
            if(check(A,now)){
                chmin(ans,now);
                break;
            }
        }
        for(ll t=n;t<=INF;t*=2){
            if(check(A,a+t)){
                chmin(ans,a+t);
                break;
            }
        }
        if(a+N<n) continue;
        for(ll x=0;(n<<(x+1))<INF;x++){
            if(A[n-a-1]+x-1>A[n-a]) continue;
            for(ll y=0;(n<<(x+y+1))<INF;y++){
                ll now=a;
                now+=((n<<x)-n);
                now+=(n<<(x+y+1));
                if(ans<=now) break;
                if(check(A,now)){
                    chmin(ans,now);
                }
            }
        }
    }
    
    if(ans==INF) ans=-1;
    return ans;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    auto rd=[&](ll momo){
        ll x=rng()%momo;
        if(x<0) x+=momo;
        return x;
    };
    
    while(0){
        int N=rd(3)+1;
        vi S(N);
        for(int i=0;i<N;i++){
            S[i]=rd(11)+1;
        }
        ll a=gutyoku(S),b=esper(S);
        if(b>1000) continue;
        if(a!=b){
            cout<<a<<" "<<b<<"\n";
            for(ll x:S) cout<<x<<" ";
            cout<<"\n";
            return 0;
        }
    }
    
    int Q;cin>>Q;
    while(Q--){
        ll N;cin>>N;
        vi S(N);
        for(int i=0;i<N;i++){
            cin>>S[i];
        }
        cout<<esper(S)<<"\n";
    }
}