結果
問題 |
No.3030 Kruskal-Katona
|
ユーザー |
|
提出日時 | 2025-02-21 22:10:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 885 bytes |
コンパイル時間 | 1,910 ms |
コンパイル使用メモリ | 193,728 KB |
実行使用メモリ | 21,884 KB |
最終ジャッジ日時 | 2025-02-21 22:10:54 |
合計ジャッジ時間 | 3,139 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:32:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 32 | scanf("%d%d",&n,&x); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const ll LLINF=0x3f3f3f3f3f3f3f3fLL; const int MAX=1e5+10; ll comb[MAX][105]; void init_comb(int n,int m) { int i,j; comb[0][0]=1; for(i=1;i<=n;i++) { comb[i][0]=1; for(j=1;j<=min(i,m);j++) { comb[i][j]=comb[i-1][j]+comb[i-1][j-1]; if(comb[i][j]>1e8) comb[i][j]=1e9; } } } ll C(int n,int m) { if(m>n||m<0||n<0) return 0; return comb[n][m]; } int res[105]; int main() { int n,x,i,j,k,now,tot; init_comb(2e4,100); scanf("%d%d",&n,&x); if(x==1) return 0*printf("%d\n",n); for(i=2e4;i>=x;i--) { if(C(i,x)>n) continue; k=i; now=0; tot=0; for(j=x;j>=1;j--) { while(k>j && now+C(k,j)>n) k--; now+=C(k,j); res[++tot]=k; if(now>=n) break; } if(now==n) { for(j=1;j<=tot;j++) printf("%d%c",res[j]," \n"[i==tot]); break; } } return 0; }