34dd53bac9 2012-06-07        kinaba: // Convert a list of distinct elements to [0..N), preserving the original order.
34dd53bac9 2012-06-07        kinaba: // O(N log N), but doesn't incur the overhead of std::map.
34dd53bac9 2012-06-07        kinaba: // Tested: TCO 2012 R2C Mid
34dd53bac9 2012-06-07        kinaba: 
34dd53bac9 2012-06-07        kinaba: template<typename T>
34dd53bac9 2012-06-07        kinaba: std::vector<int> compress(std::vector<T>& xs)
34dd53bac9 2012-06-07        kinaba: {
34dd53bac9 2012-06-07        kinaba: 	std::vector< pair<T,int> > xi;
34dd53bac9 2012-06-07        kinaba: 	for(int i=0; i<xs.size(); ++i)
34dd53bac9 2012-06-07        kinaba: 		xi.push_back( make_pair(xs[i], i) );
34dd53bac9 2012-06-07        kinaba: 	sort(xi.begin(), xi.end());
34dd53bac9 2012-06-07        kinaba: 
34dd53bac9 2012-06-07        kinaba: 	std::vector<int> result(xs.size());
34dd53bac9 2012-06-07        kinaba: 	for(int k=0; k<xi.size(); ++k)
34dd53bac9 2012-06-07        kinaba: 		result[xi[k].second] = k;
34dd53bac9 2012-06-07        kinaba: 	return result;
34dd53bac9 2012-06-07        kinaba: }