✅✅✅Easy To Understand C++ Code
Count Instead of List All Permutations:
Listing all alternating permutations would be inefficient. Instead, we count how many valid permutations start with a gi
Count Instead of List All Permutations:
Listing all alternating permutations would be inefficient. Instead, we count how many valid permutations start with a given prefix. This way, we can “skip” over groups of permutations until we reach the k-th one.

Lexicographical Order:
By considering numbers from 1 to n in increasing order and testing them one by one, we naturally generate the permutations in lexicographical (dictionary) order.

Backtracking with Counting:
For each position in the permutation, try each available number (that hasn’t been used yet) in increasing order. For each candidate, count the number of valid completions (using our helper functions) if that number is chosen.

If the number of completions is less than k, subtract that count from k and try the next candidate.
If the count is greater than or equal to k, choose that candidate and move to the next position.
Handle Insufficient Permutations:
If during this process you run out of valid choices before filling all positions (meaning there are fewer than k valid permutations), the function returns an empty list.
Selecting the First Number:
The outer loop (from 1 to n) goes through each possible starting number:

Check the candidate’s parity (odd or even).
Decrease the count (odd2 or even2) depending on whether the candidate is odd or even.
Use solve to count how many valid permutations start with that candidate.
If k is larger than the count, then skip this candidate (subtract the count from k because you are “skipping” these permutations).
Otherwise, choose this candidate, mark it as used, and update the remaining counts.
Constructing the Rest of the Permutation:
For every next position:

Loop over available numbers.
Only consider numbers that have the opposite parity to the last chosen number (to keep the alternating property).
For each candidate, calculate the count of completions.
Adjust k or choose the candidate based on whether k is larger than the count.
Return Value:
If the process completes successfully, ans will hold the k-th lexicographical alternating permutation. If not (i.e., there are fewer than k valid permutations), the function returns an empty list.
# Code
```cpp []

class Solution {
public:
    typedef long long ll;
    const ll INF = 1000000000000000000LL;
    ll helper(int a, int b) {
        __int128 res = 1;
        for (int i = 0; i < b; i++) {
            res *= (a - i);
            if (res > INF) return INF;
        }
        return (ll)res;
    }
    
    ll solve(int odd, int even, int r, int req) {
        if (r == 0) return 1;
        int nodd, neven;
        if (req == 1) {
            nodd = (r + 1) / 2;
            neven = r / 2;
        } else {
            neven = (r + 1) / 2;
            nodd = r / 2;
        }
        if (odd < nodd || even < neven) return 0;
        ll oddways = helper(odd, nodd);
        ll evenways = helper(even, neven);
        ll total = oddways;
        if (evenways == 0 || total > INF / evenways) total = INF; 
        else total *= evenways;
        return total;
    }
    
    vector<int> permute(int n, long long k) {
        vector<int> ans;
        bool first = false;
        vector<bool> used(n + 1, false);
        int odd = (n + 1) / 2, even = n / 2, last;
        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;
            int odd2 = odd, even2 = even;
            int cp = i & 1;
            int next = (cp == 1 ? 0 : 1);
            if (cp == 1) odd2--; else even2--;
            int r = n - 1;
            ll cnt = solve(odd2, even2, r, next);
            if (k > cnt) k -= cnt; 
            else {
                ans.push_back(i);
                used[i] = true;
                odd = odd2; even = even2;
                last = cp;
                first = true;
                break;
            }
        }
        if (!first) return {};
        for (int z = 1; z < n; z++) {
            bool taken = false;
            for (int j = 1; j <= n; j++) {
                if (!used[j] && ((j & 1) != last)) {
                    int odd2 = odd, even2 = even;
                    int cp = j & 1;
                    if (cp == 1) odd2--; else even2--;
                    int r = n - (z + 1);
                    int next = (cp == 1 ? 0 : 1);
                    ll cnt2 = solve(odd2, even2, r, next);
                    if (k > cnt2) k -= cnt2; else {
                        ans.push_back(j);
                        used[j] = true;
                        odd = odd2; even = even2;
                        last = cp;
                        taken = true;
                        break;
                    }
                }
            }
            if (!taken) return {};
        }
        return ans;
    }
};

```
['C++']