2040C - Ordered Permutations

295743692

A solution to the C problem of contest 992, I was really glad to finally manage to solve it (though after the contest)....so much so that I'm sharing this. Do feel free to share your views and feedback.

include <bits/stdc++.h>

using namespace std;

define ll long long int

ll fun(ll a) { if(a<1) return 1; return 2*fun(a-1); } int main() { ll tc; cin>>tc; while(tc--) { ll n,k; cin>>n>>k; ll arr[n]; vectorv; for(int i=0;i<n;i++) { arr[i]=i+1; v.push_back(arr[i]); }

if (n <= 60 && (fun(n - 1)) < k) {
        cout << -1 << endl;
        continue;
    }
    ll ind=min( n-1,(ll)( ceil( log2(1.0*k) ) ) );
    ll mx=fun( min( n-1,ind ));

    ll ref=mx/2;
    ll m=v.size();
    ll it=n-1-ind;
    while(ref>0)
    {
        if(k>ref)
        {
            swap(v[it],v[m-1]);
            m--;
            rotate(v.begin()+it,v.begin()+it+1,v.begin()+m);
            k-=ref;
        }
        else
        {
            it++;
        }
        ref/=2;
    }

    for(int i=0;i<n;i++)
        cout<<v[i]<<" ";
    cout<<endl;

}

}