(CH) Bear and Sorted Rows

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Limak has a grid that consists of N rows and N columns. He randomly wrote all numbers 1 through N^{2} in the cells of the grid, one number in each cell. You can assume that each of (N^{2})! ways was equally likely.
Limak asks you to rearrange the numbers in the grid, so that each row will be sorted either increasingly or decreasingly.
Scoring
Let (r, c) denote the cell at the intersection of the rth row and the cth column. If a number x was in (r1, c1) in the initial grid and it is in (r2, c2) in the new grid, the cost of moving x is (r1  r2)^{2} + (c1  c2)^{2}. Your score for one test is the sum of costs of moving all numbers, divided by N^{3} for clarity. The final score is the sum of scores in all tests. The goal is to minimize that score.
There are 20 tests. If your program works incorrectly (e.g. it exceeds the time limit or rows aren't sorted) on any of 20 tests, you will get a suitable verdict (e.g. TLE or WA). Otherwise, you will get AC and your score will be decided by only 20% of tests (first 4 tests). The final score will be revealed after the contest.
Input
The first line of the input contains an integer N denoting the size of the grid.
Next N lines describe the grid. The ith of those lines contains N integers t_{ i,1}, t_{ i,2}, ..., t_{ i,N}.
Output
Output N lines, describing the new grid in the same format as in the input (do not print the value N though).
The printed grid should contain all values 1 through N^{2}. Each row should be sorted either increasingly or decreasingly.
Constraints
 N = 300
 1 ≤ t_{ i,j} ≤ N^{2}
 Values t_{ i,j} are distinct.
 The initial grid was generated by randomly shuffling all N^{2} values.
Example
Input: 4 2 8 12 14 5 13 1 10 16 7 6 4 3 15 11 9 Output: 2 8 12 14 1 5 7 10 16 13 6 4 3 9 11 15
Explanation
In the provided output, each row is indeed sorted — the third row is sorted decreasingly, while other rows are sorted increasingly. Let's compute the score:
 A number 5 moved from (2,1) to (2,2) with the cost 1^{2} + 0^{2} = 1.
 A number 13 moved from (2,2) to (3,2) with the cost 1^{2} + 0^{2} = 1.
 A number 1 moved from (2,3) to (2,1) with the cost 2^{2} + 0^{2} = 4.
 A number 7 moved from (3,2) to (2,3) with the cost 1^{2} + 1^{2} = 2.
 A number 15 moved from (4,2) to (4,4) with the cost 2^{2} + 0^{2} = 4.
 A number 9 moved from (4,4) to (4,2) with the cost 2^{2} + 0^{2} = 4.
The total cost is 1 + 1 + 4 + 2 + 4 + 4 = 16. Divided by N^{3} it gives the score 16 / 64 = 0.25.
Note that this test has N = 4 only for reader's convenience. The actual tests, on which your solution will be scored, will have N = 300.
Author:  errichto 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/SORTROW 
Tags  challenge, dynamicprogramming, errichto, march17, optimization 
Date Added:  23022017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 