• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/typical/coordinate_compression.cpp from [5adf500ce372739d] to [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   }