Coordinate Compression

core

Implement vector<int> compress(const vector<int>& a) (vector<int> in C++, list of ints in Python, array of numbers in JavaScript). Build the sorted list of distinct values in a, then for each element of a, output its 0-based rank in that sorted-distinct list: the smallest distinct value has rank 0, the next distinct value has rank 1, and so on. Equal input values must receive the same rank. Use lower_bound (Python: bisect_left from the bisect module; JavaScript has no bisect, so hand-write the binary search) against the sorted-distinct list to find each element's rank. The result has the same length as a, in the same order.

Example: compress({100, -5, 100, 7}) returns {2, 0, 2, 1}.

Sorted distinct values: {-5, 7, 100}, so -5 has rank 0, 7 has rank 1, 100 has rank 2.
Reading a back in order: 100 -> 2, -5 -> 0, 100 -> 2 (same value, same rank), 7 -> 1.

Why bother: raw values like 100 and -5 are awkward to use directly as array indices: too large, or negative. Compression turns any set of values into small, dense, 0-based indices you can safely use as positions in an array (a Fenwick tree, a visited array, etc.), while preserving their relative order.

Tests include a case with n up to 2*10^5, so your solution must run in O(n log n), not O(n^2).

Input format: each test in tests/*.in is laid out as:

Line 1: the mode letter L.
Line 2: n, the array length.
Line 3: the n values, space-separated.

A performance test is instead the single line G 200000 654 (mode G): the harness builds the length-n array itself from the seed (values in [-200000, 200000]) and compares a checksum of compress's result, so your function still receives an ordinary array.

Test 03.in reads:

L
3
7 7 7

This is an array of three equal values 7 7 7; compress maps them all to rank 0.

Where you'll use it:

✦ Solution & editorial unlock with the pass.