I hate it...

matrixquerything.lisp

(defstruct cell
  color
  value
  i
  j)

(defun create-cells (matrix)
  (let ((cells (list))
        (color :white))
    (loop for i below (array-dimension matrix 0) do
          (loop for j below (array-dimension matrix 1) do
                (push (make-cell :color color :value (aref matrix i j) :i i :j j)
                      cells)
                (setf color (if (eql color :white) :black :white)))
          (if (evenp (array-dimension matrix 1))
              (setf color (if (eql color :white) :black :white))))
    cells))

(defun handle-tie (cell1 cell2)
  (if (> (cell-value cell1) (cell-value cell2)) ; not actually tie
      nil
      (let ((row1 (cell-i cell1))
            (row2 (cell-i cell2)))
        (if (< row1 row2)
            T
            (if (> row1 row2)
                nil
                (let ((col1 (cell-j cell1))
                      (col2 (cell-j cell2)))
                  (< col1 col2)))))))

(defun sort-fn (cell1 cell2)
  (if (< (cell-value cell1) (cell-value cell2))
      T
      (handle-tie cell1 cell2)))

(defun smallest-nth-cell (cells n color)
  (let* ((colored-only (remove-if-not (lambda (cell) (eql (cell-color cell) color))
                                      cells))
         (sorted (sort colored-only #'sort-fn)))
    (nth n sorted)))

(defun solution (matrix queries)
  (let ((cells (create-cells matrix)))
    (dolist (query queries)
      (let* ((ith-smallest (smallest-nth-cell cells (first query) :black))
             (jth-smallest (smallest-nth-cell cells (second query) :white))
             (average (/ (+ (cell-value ith-smallest) (cell-value jth-smallest)) 2)))
        (if (integerp average)
            (setf (aref matrix (cell-i ith-smallest) (cell-j ith-smallest)) average
                  (aref matrix (cell-i jth-smallest) (cell-j jth-smallest)) average)
            (let* ((lesser-greater (list ith-smallest jth-smallest))
                   (lesser-greater (sort lesser-greater #'sort-fn))
                   (lesser (first lesser-greater))
                   (greater (second lesser-greater)))
              (setf (aref matrix (cell-i greater) (cell-j greater)) (ceiling average)
                    (aref matrix (cell-i lesser) (cell-j lesser)) (floor average))))
        (setf cells (create-cells matrix))))
    matrix))

(equalp
  (solution #2A((2 0 4)
                (2 8 5)
                (6 0 9)
                (2 7 10)
                (4 3 4))
            '((0 0) (1 3)))
  #2A((1 2 4)
      (2 8 5)
      (6 0 9)
      (2 7 10)
      (4 3 3)))

(equalp
  (solution #2A((1 9 10 8)
                (3 4 4 4))
            '((2 3) (3 2)))
  #2A((1 9 9 7)
      (3 4 4 6)))