結果
問題 | No.3030 Kruskal-Katona |
ユーザー |
![]() |
提出日時 | 2025-02-21 22:43:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 656 bytes |
コンパイル時間 | 2,557 ms |
コンパイル使用メモリ | 192,996 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 22:43:40 |
合計ジャッジ時間 | 3,790 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios::sync_with_stdio(false); std::cin.tie(nullptr); } const int INF = 1e9; long long binom(int n, int k) { long long res = 1; for (int i = 1; i <= k; ++i) { res *= n - (k - i); res /= i; if (res > INF) { return INF; } } return res; } void solve(int n, int i) { if (n == 0) { return; } int ok = i, ng = n + 1; while (ng - ok > 1) { int mid = (ok + ng) / 2; if (binom(mid, i) <= n) { ok = mid; } else { ng = mid; } } cout << ok << " "; solve(n - binom(ok, i), i - 1); } int main() { fast_io(); int n, i; cin >> n >> i; solve(n, i); cout << endl; }