• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Aug 17th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <algorithm>
3.
4. using namespace std;
5.
6. const int N = 1<<16;
7. int n, m, k, a[20];
8. int64_t cnt[20][N];
9. bool g[20][20], u[20][N];
10.
11.
12. bool vkl(int a, int x){
13.     return x&(1<<a);
14.     }
15.
16. int64_t kl(int p, int x){
17.     if(x==(1<<n)-1){ u[p][x] = 1; cnt[p][x] = 1; return 1LL;}
18.     if(u[p][x]) return cnt[p][x];
19.     int res = 0;
20.     for(int i = 0; i < n; ++i){
21.         if(!vkl(i,x)&&g[p][i]) res+=kl(i,x+(1<<i));
22.     }
23.     cnt[p][x] = res;
24.     u[p][x] = 1;
25.     return cnt[p][x];
26.     }
27.
28. int main(){
29.     ios_base::sync_with_stdio(0);
30.     cin.tie(0);
31.     cin >> n >> m >> k;
32.     for(int i = 0; i < n; ++i)
33.         cin >> a[i];
34.     sort(a,a+n);
35.     for(int i = 0; i < n; ++i)
36.         for(int j = 0; j < n; ++j)
37.             g[i][j] = __gcd(a[i],a[j])>=k;
38.     int64_t ans = 0;
39.     for(int i = 0; i < n; ++i) ans+=kl(i,1<<i);
40.     if(m>ans){ cout << -1; return 0;}
41.     int64_t knt = 1;
42.     int mn = 0, ps = 0;
43.     for(int i = 0; i < n; ++i){
44.         for(int j = 0; j < n; ++j){
45.             if(vkl(j,mn)||(i&&!g[ps][j])) continue;
46.             knt += cnt[j][mn+(1<<j)];
47.             if(knt>m){ cout << a[j] << " "; ps = j; knt-=cnt[j][mn+(1<<j)]; mn+=1<<j; break;}
48.         }
49.     }
50.
51.     return 0;
52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?