Artifact Content
Not logged in

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