結果
問題 |
No.2025 Select $k$-th Submultiset
|
ユーザー |
![]() |
提出日時 | 2022-07-29 22:45:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,281 bytes |
コンパイル時間 | 4,002 ms |
コンパイル使用メモリ | 253,936 KB |
最終ジャッジ日時 | 2025-01-30 15:34:36 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 TLE * 9 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int N,L; long long k; long long get(long long n){ //cout<<'a'<<','<<n<<endl; long long ret = 1; rep(i,N-1){ ret *= n-i; } rep(i,N-1){ ret /=i+1; } return ret; } long long get(vector<long long> l,vector<long long> r){ long long ret = 0; rep(i,1<<N){ long long LL = L; int t = 0; rep(j,N){ if((i>>j)&1){ LL -= l[j]; } else{ t++; LL -= r[j]+1; } } if(LL<0)continue; long long c = get(LL+N-1); if(t%2==1)c*=-1; ret += c; } return ret; } int main() { cin>>N>>L; vector<long long> c(N); rep(i,N)cin>>c[i]; int Q; cin>>Q; rep(_,Q){ cin>>k; vector<long long> l(N,0),r=c; //cout<<get(l,r)<<endl; if(get(l,r)<k){ cout<<-1<<endl; continue; } vector<long long> ans; rep(i,N){ long long ok = 0,ng = r[i]+1; while(ng-ok>1LL){ long long mid = (ok+ng)/2; l[i] = mid; if(get(l,r)>=k)ok = mid; else ng = mid; } l[i] = ok+1; k -= get(l,r); l[i] = ok; r[i] = ok; } rep(i,N){ if(i!=0)cout<<' '; cout<<l[i]; } cout<<endl; } return 0; }