blablabla

$O(n^3)$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll f[21][21][3];

void prework()
{
    f[1][1][1] = f[1][1][0] = 1;
    for(int i=2; i<=20; i++)
        for(int j=1; j<=i; j++)
        {
            for(int p=1; p<=j-1; p++)
            f[i][j][1]+=f[i-1][p][0];
            for(int p=j; p<=i-1; p++)
            f[i][j][0]+=f[i-1][p][1];
        }
}

int main()
{
    int t;
    prework();
    cin >> t;
    while(t--)
    {
        bool vis[21];memset(vis,0,sizeof vis);
        ll n,m,last,k;
        cin >> n >> m;
        for(int j=1; j<=n; j++)
        {
            if(f[n][j][1]>=m)
            {
                last=j,k=1;
                break;
            }
            else m-=f[n][j][1];
            if(f[n][j][0]>=m)
            {
                last=j,k=0;
                break;
            }
            else m-=f[n][j][0];
        }
        vis[last]=1;cout<<last;
        for(int i=2; i<=n; i++)
        {
            k=1-k;
            int j=0;
            for(int len=1; len<=n; len++)
            {
                if(vis[len])continue;
                j++;
                if(k==0 && len<last || k==1 && len>last)
                {
                    if(f[n-i+1][j][k]>=m)
                    {
                        last=len;
                        break;
                    }
                    else m-=f[n-i+1][j][k];
                }
            }
            vis[last]=1;
            cout<<" "<<last;
        }
        cout<<endl;
    }
    return 0;
}