結果
問題 |
No.2025 Select $k$-th Submultiset
|
ユーザー |
![]() |
提出日時 | 2022-07-29 23:19:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 980 ms / 2,000 ms |
コード長 | 2,341 bytes |
コンパイル時間 | 1,712 ms |
コンパイル使用メモリ | 173,060 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-19 16:51:34 |
合計ジャッジ時間 | 23,834 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:76:11: warning: 'cnt' may be used uninitialized [-Wmaybe-uninitialized] 76 | if (cnt <= k){ | ^~ main.cpp:66:21: note: 'cnt' was declared here 66 | long long cnt; | ^~~
ソースコード
#include <bits/stdc++.h> using namespace std; long long count(vector<int> c, int L){ int N = c.size(); int F = 1; for (int i = 0; i < N - 1; i++){ F *= i + 1; } long long ans = 0; for (int i = 0; i < (1 << N); i++){ int L2 = L; for (int j = 0; j < N; j++){ if ((i >> j & 1) == 1){ L2 -= c[j]; } } if (L2 >= 0){ long long p = 1; for (int j = 0; j < N - 1; j++){ p *= L2 + j + 1; } p /= F; if (__builtin_parity(i) == 0){ ans += p; } else { ans -= p; } } } return ans; } int main(){ int N, L; cin >> N >> L; vector<int> c(4, 1); for (int i = 4 - N; i < 4; i++){ cin >> c[i]; c[i]++; } long long sum = count(c, L); int Q; cin >> Q; for (int i = 0; i < Q; i++){ long long k; cin >> k; k--; if (k >= sum){ cout << -1 << endl; } else { int L2 = L; vector<int> ans(4, 0); for (int j = 0; j < 4; j++){ int p = 0; if (L2 < c[j]){ if (k == 0){ ans[j] = L2; break; } k--; p = 1; } int tv = min(L2, c[j]); int fv = 0; while (tv - fv > 1){ int mid = (tv + fv) / 2; long long cnt; if (j == 0){ cnt = sum - count(vector<int>{mid, c[1], c[2], c[3]}, L2) - p; } if (j == 1){ cnt = count(vector<int>{c[1], c[2], c[3]}, L2) - count(vector<int>{mid, c[2], c[3]}, L2) - p; } if (j == 2){ cnt = count(vector<int>{c[2], c[3]}, L2) - count(vector<int>{mid, c[3]}, L2) - p; } if (cnt <= k){ tv = mid; } else { fv = mid; } } ans[j] = fv; if (j == 0){ k -= sum - count(vector<int>{tv, c[1], c[2], c[3]}, L2) - p; } if (j == 1){ k -= count(vector<int>{c[1], c[2], c[3]}, L2) - count(vector<int>{tv, c[2], c[3]}, L2)- p; } if (j == 2){ k -= count(vector<int>{c[2], c[3]}, L2) - count(vector<int>{tv, c[3]}, L2) - p; } L2 -= fv; } for (int j = 4 - N; j < 4; j++){ cout << ans[j]; if (j < 3){ cout << ' '; } } cout << endl; } } }