Artifact 60ffa78d3698d241174c659aa047a730ec7a2cbe
// Convert a list of N elements with K distinct elements to [origin .. origin+K),
// preserving the original order. O(N log N), but doesn't incur the overhead of std::map.
// Tested: TCO 2012 R2C Mid, SRM 584 Mid
template<typename T>
vector<int> compress(const vector<T>& xs, int origin = 0)
{
vector< pair<T,int> > xi;
for(int i=0; i<xs.size(); ++i)
xi.push_back( make_pair(xs[i], i) );
sort(xi.begin(), xi.end());
vector<int> result(xs.size());
for(int k=0,id=origin; k<xi.size(); ++k) {
if(0<=k-1 && xi[k-1].first<xi[k].first)
++id;
result[xi[k].second] = id;
}
return result;
}