Diff
Not logged in

Differences From Artifact [5adf500ce372739d]:

To Artifact [60ffa78d3698d241]:


1 -// Convert a list of distinct elements to [0..N), preserving the original order. 2 -// O(N log N), but doesn't incur the overhead of std::map. 3 -// Tested: TCO 2012 R2C Mid 1 +// Convert a list of N elements with K distinct elements to [origin .. origin+K), 2 +// preserving the original order. O(N log N), but doesn't incur the overhead of std::map. 3 +// Tested: TCO 2012 R2C Mid, SRM 584 Mid 4 4 5 5 template<typename T> 6 -std::vector<int> compress(std::vector<T>& xs) 6 +vector<int> compress(const vector<T>& xs, int origin = 0) 7 7 { 8 - std::vector< pair<T,int> > xi; 8 + vector< pair<T,int> > xi; 9 9 for(int i=0; i<xs.size(); ++i) 10 10 xi.push_back( make_pair(xs[i], i) ); 11 11 sort(xi.begin(), xi.end()); 12 12 13 - std::vector<int> result(xs.size()); 14 - for(int k=0; k<xi.size(); ++k) 15 - result[xi[k].second] = k; 13 + vector<int> result(xs.size()); 14 + for(int k=0,id=origin; k<xi.size(); ++k) { 15 + if(0<=k-1 && xi[k-1].first<xi[k].first) 16 + ++id; 17 + result[xi[k].second] = id; 18 + } 16 19 return result; 17 20 }