fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6. ios::sync_with_stdio(false);
  7. cin.tie(nullptr);
  8.  
  9. int T;
  10. cin >> T;
  11. while (T--) {
  12. ll n, k;
  13. cin >> n >> k;
  14. // total number of such "zig-zag" perms is 2^(n−1)
  15. ll total = 1LL << (n - 1);
  16. if (k > total) {
  17. cout << -1 << "\n";
  18. continue;
  19. }
  20.  
  21. // zero‐index k
  22. k--;
  23.  
  24. vector<int> ans(n);
  25. int L = 0, R = n - 1;
  26. // build from i=1..n
  27. for (int i = 1; i <= n; i++) {
  28. // each choice of placing 'i' either at left or right
  29. // accounts for exactly 2^(n-i) permutations
  30. ll block = 1LL << (n - i);
  31. ll idx = k / block; // 0 means "put at left", 1 means "put at right"
  32.  
  33. if (idx == 0) {
  34. ans[L++] = i;
  35. } else {
  36. ans[R--] = i;
  37. }
  38. k %= block;
  39. }
  40.  
  41. // output
  42. for (int i = 0; i < n; i++) {
  43. cout << ans[i] << (i+1<n ? ' ' : '\n');
  44. }
  45. }
  46. return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5316KB
stdin
6
3 2
3 3
4 11
4 6
6 39
7 34
stdout
1 2 3
1 3 2
-1
1 3 4 2
-1
1 3 4 5 6 7 2