Artifact 60ffa78d3698d241174c659aa047a730ec7a2cbe

• File lib/typical/coordinate_compression.cpp
  • 2013-07-10 13:36:20 - part of checkin [2cbc47d903] on branch trunk - Coordinate Compression for duplicated elements. (user: kinaba) [annotate]

// 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;
}