Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- vector<int>freq[26];
- long long N, dp[1<<20];
- string ans;
- long long solve(int mask, int k) {
- long long &ret = dp[mask];
- if(mask==(1<<N)-1) return ret = 1;
- if(ret!=0) return ret;
- for(int i=0; i<26; ++i) if(!freq[i].empty()) {
- int idx = freq[i].back();
- freq[i].pop_back();
- ret += solve(mask | (1<<idx), k-ret);
- freq[i].push_back(idx);
- }
- return ret;
- }
- void construct(int mask, int k) {
- if(mask==(1<<N)-1) return;
- for(int i=0; i<26; ++i) if(!freq[i].empty()) {
- int idx = freq[i].back();
- freq[i].pop_back();
- long long got = dp[mask | (1<<idx)];
- if(got >= k) {
- ans += 'a' + i;
- construct(mask | (1<<idx), k);
- return;
- }
- k -= got;
- freq[i].push_back(idx);
- }
- }
- void PlayGround() {
- string s; cin >> s;
- int k; cin >> k;
- N = s.size();
- for(int i=0; i<(1<<N); ++i) dp[i] = 0;
- for(int i=0; i<N; ++i) {
- freq[s[i]-'a'].push_back(i);
- }
- if(solve(0, k) < k) {
- cout << "Impossible\n";
- } else {
- construct(0, k);
- cout << ans << '\n';
- }
- ans.clear();
- for(auto &it : freq) it.clear();
- // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- }
- int main() {
- int T; cin >> T;
- for(int i=1; i<=T; ++i) {
- cout << "Case " << i << ": ";
- PlayGround();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
