2cbc47d903 2013-07-10        kinaba: // Convert a list of N elements with K distinct elements to [origin .. origin+K),
2cbc47d903 2013-07-10        kinaba: // preserving the original order.  O(N log N), but doesn't incur the overhead of std::map.
2cbc47d903 2013-07-10        kinaba: // Tested: TCO 2012 R2C Mid, SRM 584 Mid
34dd53bac9 2012-06-07        kinaba: 
34dd53bac9 2012-06-07        kinaba: template<typename T>
2cbc47d903 2013-07-10        kinaba: vector<int> compress(const vector<T>& xs, int origin = 0)
34dd53bac9 2012-06-07        kinaba: {
2cbc47d903 2013-07-10        kinaba: 	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: 
2cbc47d903 2013-07-10        kinaba: 	vector<int> result(xs.size());
2cbc47d903 2013-07-10        kinaba: 	for(int k=0,id=origin; k<xi.size(); ++k) {
2cbc47d903 2013-07-10        kinaba: 		if(0<=k-1 && xi[k-1].first<xi[k].first)
2cbc47d903 2013-07-10        kinaba: 			++id;
2cbc47d903 2013-07-10        kinaba: 		result[xi[k].second] = id;
2cbc47d903 2013-07-10        kinaba: 	}
34dd53bac9 2012-06-07        kinaba: 	return result;
34dd53bac9 2012-06-07        kinaba: }