This is just how I solved 2268F. Not the shortest way, it only has to fit in the move limit.

m = 2n. The grid is m by m and every column is a permutation of 1..m. A move picks (i, j) and swaps row i with row i+1 in columns j and j+1. We want a[i][j] = i. You get at most 2n^3 + 9n moves, and you do not need the minimum.

When it is impossible

Xor the inversion parity of every column. A move always flips two columns. The two values you swap inside one column are different, since the column is a permutation, so both parities change and the xor stays the same. A sorted grid has xor 0. If the xor is 1, print -1.

Building the moves

Fix values from the top, x = 1, 2, ..., m-2. When you start x, rows 1..x-1 are already correct, so in each column the x is somewhere on row x or lower. I only touch rows >= x, except a few times when I borrow a neighbor that is already done and put it back right after.

I split the columns into pairs (1, 2), (3, 4), ..., (m-1, m). A move on the left column of a pair moves both columns of that pair. That is the whole trick. You almost never move one column by itself.

Middle pairs, left column j = 3, 5, ..., m-3. Let p be the row of x in column j, and q the row of x in column j+1.

If both are already on row x, nothing to do. In the code I actually swap that pair down once, and the both-missing case swaps it back later. Those two moves cancel. I just did not special-case it.

If only the left cell is x, I have to pull column j+1 up and leave column j alone. If column j+3 is not already x, I bubble column j+1 up with moves (i, j+1). Column j+2 gets dragged along, but that pair is not finished yet, so it is fine. If column j+3 is already x, I cannot trash column j+2. So I first put the x from column j+1 and the x from column j+2 on the same row. Whichever one is deeper, I walk it up on the outside. If j+1 is deeper I use moves on column j, and those moves are below row x, so the finished cell stays. If j+2 is deeper I use moves on column j+2, same idea, the cell (x, j+3) stays. Once they line up at some depth d > x, move (d-1, j+1) lifts both, and I repeat that until they sit on row x.

If only the right cell is x, same thing mirrored. I do these pairs from right to left, so the pair on the right is already finished. If the pair (j-2, j-1) is not finished, I bubble column j up with moves (i, j-1). If that left pair is finished, I borrow it. If the x I want is sitting right under row x, I push it one row lower first, otherwise the next swap eats it. Then I do move (x, j-1). The finished x in column j-1 drops to row x+1. I bubble the real x up to row x+1, and I only use moves whose top row is at least x+1, so the finished cell in column j+1 is safe. Then I do (x, j-1) again. x lands on row x, and column j-1 is back where it was.

If neither cell has x on row x, I equalize the two depths the same way, walking the deeper one up on the outer side, and then lift both together.

The border pairs are more annoying. (1, 2) has nothing on the left, and (m-1, m) has nothing on the right. If exactly one of the two cells is already x, I park that token on row x+1. If the other token is sitting on row x+1 I kick it down, then I swap row x with row x+1. Now both tokens are strictly below row x, so I can equalize and lift like before. One thing that bit me: while equalizing, a joint swap can drag the shallower token one extra row down. I just add 1 to the depth I had stored for it.

Last two rows

After x = m-2, every column is some order of {m-1, m}. A column is bad if the bottom cell is m-1. That is one inversion, and the global xor is 0, so the number of bad columns is even. I scan j from 1 to m-1, and if column j is bad I do move (m-1, j). It fixes j and flips j+1, so the defect slides right. An even count means the last column is already good when the scan ends. I never need a move that falls off the right edge.

n = 1 is just a 2x2, and there is only one legal move. Parity still catches the impossible case. Otherwise that one move sorts both columns, or the grid is already sorted and I print 0.

The number of moves is O(n^3). The cap is 2n^3 + 9n, and this stays under it. Sum of n^3 over the tests is at most 80^3, so the time limit is fine too.