Official Analysis (C++)

Explanation

Two elements can only collide if they share the same remainder modulo $|K|$, so we handle each remainder class independently. We are motivated to do so, since adding $K$ to each element doesn't change its remainder when divided by $K$. In particular, we have

and so we can consider the elements by their respective remainder.

Within each class, sort the elements in the direction of $K$ (ascending if $K > 0$, descending if $K < 0$). Then, iterate in sorted order, advancing each element only as much as strictly needed to make it distinct from the previous one. This greedy approach is optimal, since we never move an element more than necessary.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {