How do you construct an array with one inversions? How about three? How about six?

You can only scramble the order of the small numbers and keep the large ones ordered. Try the sample test case.

In the sample, you can construct 3 2 4 1 5. Where 1, 2, 3 are in reverse order and 4 adds an inversion by being before 1. Try to generalize this.

We start with $$$a_i=i$$$ with $$$0$$$ inversions. First, find the largest $$$m$$$ such that $$$\frac{m(m-1)}{2}\leq k$$$. Reverse the first $$$m$$$ numbers to get $$$\frac{m(m-1)}{2}$$$ inversions. $$$m$$$ can be found by brute force.

And then let $$$k'=k-\frac{m(m-1)}{2}$$$, this is how many inversion you needed left. Swap the number $$$m+1$$$ just $$$k'$$$ spots to the left and we're done.

(You can use a stack or vector to reverse as well, as shown in the code).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int a[1000005];

int main(){
    vector <int> pre;
    int n, id;
    ll tg;
    cin>>n>>tg;
    id=0;
    while(tg-id>0){
        pre.pb(id+1);
        tg-=id;
        id++;
    }
    for(int i=1; i<=n; i++) a[i]=i;
    reverse(a+1, a+id+1);
    int k=tg;
    id++;
    while(k>0){
        swap(a[id], a[id-1]);
        id--;
        k--;
    }
    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
}

Solve the problem for $$$n=9$$$ and $$$k=3$$$.

Put numbers in $$$\mod k$$$ order would be good. For example you have 3 6 9 1 4 7 2 5 8 for $$$n=9, k=3$$$. However, sometimes it won't work.

If $$$k \lt \sqrt{n}$$$ it becomes impossible. For proof, search for the Erdős–Szekeres Theorem.

See hint 3 for impossible cases.

For the possible cases. Put all numbers that are $$$0 \mod k$$$ in increasing order, then all numbers that are $$$1\mod k$$$ in increasing order, then put $$$2 \mod k$$$ ones, and so on.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main(){
    int t;
    cin>>t;
    while(t--){
        vector <int> v;
        int n,k;
        cin>>n>>k;
        if(k*k<n){
            cout<<"IMPOSSIBLE\n";
            continue;
        }
        for(int i=0; i<k; i++){
            for(int j=1; j<=k; j++){
                v.pb(j*k-i);
            }
        }
        for(int i: v){
            if(i<=n) cout<<i<<" ";
        }
        cout<<'\n';
    }
}