結果

問題 No.2025 Select kk-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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0