Advertisement
Guest User

Untitled

a guest
Aug 17th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement