結果
問題 | No.2025 Select -th Submultiset |
ユーザー |
![]() |
提出日時 | 2022-07-29 23:02:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,369 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 33,536 KB |
実行使用メモリ | 12,736 KB |
最終ジャッジ日時 | 2024-07-19 16:21:55 |
合計ジャッジ時間 | 5,649 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <stdio.h>int ans[110];int x[100010];long long int count[6][100010],sum[6][100010];int main(){int a,b;scanf("%d%d",&a,&b);for(int i=1;i<=a;i++) scanf("%d",&x[i]);for(int i=0;i<=x[a];i++) count[a][i] = 1;sum[a][0] = count[a][0];for(int i=1;i<=b;i++) sum[a][i] = count[a][i] + sum[a][i-1];for(int j=a-1;j>=0;j--){for(int i=0;i<=b;i++){int L = i-x[j]>0?i-x[j]:0; // L ~ iif(L==0) count[j][i] = sum[j+1][i];else count[j][i] = sum[j+1][i] - sum[j+1][L-1];}sum[j][0] = count[j][0];for(int i=1;i<=b;i++) sum[j][i] = count[j][i] + sum[j][i-1];}int c;scanf("%d",&c);while(c--){long long int d;scanf("%lld",&d);if(d>count[1][b]){printf("-1\n");continue;}d--;int limit = b;for(int i=2;i<=a;i++){int R = limit<x[i-1]?limit:x[i-1];int p = R+1;int min = 0, max = R;while(min<=max){int h = (min+max)/2;long long int val;if(limit==R) val = sum[i][limit-h];else val = sum[i][limit-h] - sum[i][limit-R-1];if(val<=d){p = h;max = h-1;}else min = h+1;}long long int val;if(limit==R) val = sum[i][limit-p];else val = sum[i][limit-p] - sum[i][limit-R-1];//printf("%d %d %lld!!\n",i,p,val);printf("%d ",p-1);d -= val;limit -= (p-1);}printf("%d\n",limit);}}