結果

問題 No.3030 Kruskal-Katona
コンテスト
ユーザー Zhiyuan Chen
提出日時 2025-02-21 22:46:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,901 bytes
コンパイル時間 1,084 ms
コンパイル使用メモリ 70,944 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-21 22:46:20
合計ジャッジ時間 2,144 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // 添加此头文件
using namespace std;

typedef long long ll;

ll comb(ll n, int k) {
    if (k == 0 || k == n) return 1;
    k = min(k, (int)(n - k));
    ll res = 1;
    for (int i = 1; i <= k; ++i) {
        if (res > LLONG_MAX / (n - k + i)) {
            return LLONG_MAX;
        }
        res *= (n - k + i);
        res /= i;
    }
    return res;
}

vector<ll> solve(ll N, int i) {
    vector<ll> res;
    ll remaining = N;
    int current_k = i;
    
    while (remaining > 0 && current_k >= 1) {
        ll left = current_k;
        ll right = current_k + 100;
        ll best_n = current_k;
        
        // 动态扩展右边界
        while (true) {
            ll c = comb(right, current_k);
            if (c == LLONG_MAX || c > remaining) break;
            right *= 2;
            if (right > 1e18) break;
        }
        
        // 二分查找
        while (left <= right) {
            ll mid = (left + right) / 2;
            ll c = comb(mid, current_k);
            
            if (c == LLONG_MAX) { // 溢出处理
                right = mid - 1;
                continue;
            }
            
            if (c <= remaining) {
                best_n = max(best_n, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (best_n < current_k) {
            current_k--;
            continue;
        }
        
        res.push_back(best_n);
        remaining -= comb(best_n, current_k);
        current_k--;
    }
    
    return res;
}

int main() {
    ll N;
    int i;
    cin >> N >> i;
    
    auto ans = solve(N, i);
    
    for (size_t idx = 0; idx < ans.size(); ++idx) {
        cout << ans[idx];
        if (idx != ans.size() - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}
0