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';
    }
}

For $$$a=[1,2,3,4], b=[4,3,1,2]$$$. Note that $$$[2,1,4,3]$$$ is a solution.

Build a graph with edges from $$$a_i$$$ to $$$b_i$$$ for every $$$i$$$, how do you construct a solution for the test case in hint 1? When does it not work?

Build a graph from $$$a_i$$$ to $$$b_i$$$ for every $$$i$$$. And then if there isn't any $$$2$$$-cycles in the graph, just make $$$c_i$$$ the index of the vertex where you walk $$$2$$$ steps from $$$a_i$$$.

If there is a $$$2$$$ cycle then $$$c_i=a_i$$$ for those two vertices. Store those pairs into a queue or vector, and then merge two pairs to make a new $$$4$$$-cycle any way you want. One pair might be left, then you need to merge the last pair into an existing cycle as well. $$$n=2$$$ is impossible.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
 
const int MAXN=200005;
int a[MAXN], b[MAXN], pos[MAXN], g[MAXN], ans[MAXN], bad[MAXN];
queue <pii> qu;
 
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){
        cin>>b[i];
        pos[b[i]]=i;
        g[a[i]]=b[i];
    }
    for(int i=1; i<=n; i++){
        ans[i]=g[g[a[i]]];
        if(ans[i]==a[i]){
            if(!bad[i]) qu.push({i, pos[a[i]]});
            bad[pos[a[i]]]=1;
            bad[i]=1;
        }
    }
    pii temp1, temp2;
    while(qu.size()>1){
        temp1=qu.front();
        qu.pop();
        temp2=qu.front();
        qu.pop();
        swap(ans[temp1.first], ans[temp2.first]);
        swap(ans[temp2.second], ans[temp1.second]);
        bad[temp1.first]=bad[temp2.first]=bad[temp1.second]=bad[temp2.second]=0;
    }
    if(!qu.empty()){
        int x1=0, x2=0;
        if(n==2){
            cout<<"IMPOSSIBLE";
            return 0;
        }
        temp1=qu.front();
        qu.pop();
        for(int i=1; i<=n; i++){
            if(x1 && x2) break;
            if(!bad[i]){
                if(x1) x2=i;
                else x1=i;
            }
        }
        swap(ans[temp1.first], ans[x1]);
        swap(ans[temp1.second], ans[x2]);
    }
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
}

Solve when $$$n=p-1$$$ where $$$p$$$ is a prime.

A recursive solution is possible. How do you deal with the last few terms first?

Use any sieve method to find all primes below $$$10^6$$$.

If $$$n+1$$$ is a prime then you solve directly by letting the first permutation be identity permutation and the second one be reversed.

Otherwise, put the second one and the first both as identity first. Find an $$$i \lt n$$$ such that $$$n+i$$$ is prime, reverse the subarray from the $$$i$$$th term to the $$$n$$$th term and solve it for $$$n=i-1$$$ (recursively doing so until $$$n+1$$$ is prime where you hit the base case).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int MAXN=200005;
bool prime[MAXN];
int ans[MAXN];
 
void solve(int n){
    if(prime[n+1]){
        for(int i=1; i<=n; i++) ans[i]=n-i+1;
        return;
    }
    for(int i=2; i<=n; i++){
        if(prime[n+i]){
            reverse(ans+i, ans+n+1);
            solve(i-1);
            break;
        }
    }
}
 
int main(){
    for(int i=2; i<MAXN; i++) prime[i]=1;
    for(int i=2; i*i<MAXN; i++){
        if(prime[i]){
            for(int j=i*i; j<MAXN; j+=i) prime[j]=0;
        }
    }
    ll n;
    cin>>n;
    for(int i=1; i<=n; i++) ans[i]=i;
    solve(n);
    for(int i=1; i<=n; i++) cout<<i<<" ";
    cout<<'\n';
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
}