結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
コンテスト
ユーザー carrot46
提出日時 2021-07-30 23:03:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,184 bytes
コンパイル時間 2,248 ms
コンパイル使用メモリ 211,776 KB
最終ジャッジ日時 2025-01-23 12:48:14
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
//#pragma GCC optimize("Ofast")
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
using P = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void my_printv(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N;
    vector<int> c(10, 0), d(10, 0);
    rep(i, 9) cin>>c[i + 1];
    unordered_map<ll, unordered_set<unsigned int> > memo;
    auto my_hash = [](vector<int> &v){
        ll res{};
        reps(i, 1, 10) (res *= 15) += v[i];
        return res;
    };
    unsigned int sum{}, ten{1}, mask{1};
    rep(i, (N + 1) / 2) ten *= 10;
    bool mitai = false;
    auto dfs = [&](auto &&self, bool bef, int num) -> bool{
        if(num == 0){
            if(bef) memo[my_hash(d)].insert(sum&mask);
            else {
                ll tmp = my_hash(c);
                /*
                my_printv(c);
                cout<<sum<<endl;
                */
                 if(memo[tmp].find((mask - ((sum * ten)&mask) + 1)&mask) != memo[tmp].end()){
                    return true;
                }
            }
        }else{
            bool ok = false;
            reps(i, 1, 10) {
                if (bef ? c[i] > d[i] : c[i] > 0) {
                    bef ? ++d[i] : --c[i];
                    unsigned int tmp = sum;
                    ((sum *= 10) += i)&=mask;
                    if(self(self, bef, num - 1)) ok = true;
                    sum = tmp;
                    bef ? --d[i] : ++c[i];
                }
                if(ok) return true;
            }
        }
        return false;
    };
    int lb = 0, ub = 31;
    while(ub - lb > 1) {
        memo.clear();
        sum = 0;
        int cen = (ub + lb) / 2;
        //mitai = cen == 16;
        mask = (1<<cen) - 1;
        dfs(dfs, true, (N + 1) / 2);
        /*
        if(mitai) {
            cout<<mask<<endl;
            for (auto val : memo[my_hash({0, 0, 0, 1, 0, 1, 1, 0, 0, 0})]) cout << val << endl;
        }
         */
        (dfs(dfs, false, N / 2) ? lb : ub) = cen;
    }
    if(lb == 30){
        auto check = [&](ll num){
            rep(i, 10) d[i] = 0;
            while(num){
                ++d[num%10];
                num /= 10;
            }
            return d == c;
        };
        ll x = 1LL<<lb;
        for(ll num = x; num < 1e+15; num += x){
            if(check(num)) chmax(lb, __builtin_ctzll(num));
        }
    }
    cout<<lb<<endl;
}
0