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]<<" ";
}

As you might question in the solution: why does there always an $$$1\leq i \lt n$$$ such that $$$n+i$$$ is prime? Bertrand's Postulate tell us there is a prime $$$p$$$ such that $$$n \lt p \lt 2n$$$ for all $$$n \gt 1$$$. I don't know how to prove the theorem though so don't ask me.

We first disregard the limit that each pair of player can play only one game. Develop a greedy solution (with the fact that the sum of $$$x_i$$$ is not too large.

Set the limit back. We know that the player who want to play the most matches matters, so we need to deal with them first. Can you deal with them greedily?

What if a player want to play a lot of games and there are not enough opponents left during your greedy?

From now on, if a player still wants to play $$$k$$$ games I said they have $$$k$$$ "remnant games".

Use a priority queue to store how many remnants game are left for each player. Take out the one with the most remnant games and pair opponents with them (pair the opponents in decreasing order of remnant games). If at any moment the player with the most remnant games can't find enough opponents, then halt and output IMPOSSIBLE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
 
int tot;
int oddcnt;
priority_queue <pii> pq;
vector <pii> ans;
vector <pii> temp;
 
int main(){
    int n;
    cin>>n;
    int num;
    bool possible=true;
    for(int i=1; i<=n; i++){
        cin>>num;
        if(num>0) pq.push({num, i});
    }
    pii cur, nxt;
    while(!pq.empty()){
        cur=pq.top();
        pq.pop();
        if(cur.first>pq.size()){
            possible=false;
            break;
        }
        else{
            for(int i=0; i<cur.first; i++){
                nxt=pq.top();
                pq.pop();
                ans.pb({cur.second, nxt.second});
                if(nxt.first>1) temp.pb({nxt.first-1, nxt.second});
            }
            while(temp.size()>0){
                pq.push(temp.back());
                temp.pop_back();
            }
        }
    }
    if(possible){
        cout<<ans.size()<<'\n';
        for(pii x: ans){
            cout<<x.first<<" "<<x.second<<'\n';
        }
    }
    else cout<<"IMPOSSIBLE";
}

Start with a wrong board. Try applying swaps to it. Which swaps would you want to perform?

You'd only like the ones that increases the number of distinct row/column sums. But we don't know how to find them at all, so what do we do?

$$$n \lt 4$$$ can be checked to be impossible.

Start with a board where every cell on the $$$i$$$th row is filled in with number $$$i$$$. This board would be incorrect but it's okay. We repeatedly randomly choose two cells to swap. If swapping them increase the number of distinct row/column sums then we swap them, otherwise we don't swap them. $$$50000$$$ random tries passes as my code do get AC.

A bit on implementation, though. Carefully store the row/column sums and the number of distinct sum values. When you test performing a swap make sure to do it in $$$O(1)$$$ by these store values.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int MAXN=1005;
int g[MAXN][MAXN];
int r[MAXN], c[MAXN], r1, r2, c1, c2;
int cnt=0, ori;
int ex[1000005];
 
void rem(int x){
    ex[x]--;
    if(ex[x]==0) cnt--;
}
 
void add(int x){
    ex[x]++;
    if(ex[x]==1) cnt++;
}
 
int res;
void change(int x1, int y1, int x2, int y2){
    rem(r[x1]); rem(r[x2]); rem(c[y1]); rem(c[y2]);
    r[x1]+=(g[x2][y2]-g[x1][y1]);
    c[y1]+=(g[x2][y2]-g[x1][y1]);
    r[x2]-=(g[x2][y2]-g[x1][y1]);
    c[y2]-=(g[x2][y2]-g[x1][y1]);
    add(r[x1]); add(r[x2]); add(c[y1]); add(c[y2]);
    swap(g[x1][y1], g[x2][y2]);
}
 
int main(){
    int n;
    cin>>n;
    if(n<=3){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            g[i][j]=i;
            r[i]+=g[i][j];
            c[j]+=g[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        add(r[i]);
        add(c[i]);
    }
    int sp=0;
    while(cnt<2*n && sp<50000){
        r1=rand()%n+1;
        c1=rand()%n+1;
        r2=rand()%n+1;
        c2=rand()%n+1;
        ori=cnt;
        change(r1, c1, r2, c2);
        if(cnt<ori) change(r1, c1, r2, c2);
        sp++;
    }
    if(cnt<2*n){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout<<g[i][j]<<" ";
        }
        cout<<'\n';
    }
}