Overview
| SHA1 Hash: | 34dd53bac90db86023d81b8c60b1dcde9ee96d7d |
|---|---|
| Date: | 2012-06-07 14:24:24 |
| User: | kinaba |
| Comment: | TCO12-2C |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/TCO12-2C-U/1A.cpp version [0061f6e7ce3b6290]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class GreedyTravelingSalesman { public: > 23 int worstDistance(vector <string> thousands, vector <string> hundreds, v > 24 { > 25 int N = thousands.size(); > 26 vector< vector<int> > d(N, vector<int>(N)); > 27 for(int a=0; a<N; ++a) > 28 for(int b=0; b<N; ++b) > 29 d[a][b] = (thousands[a][b]-'0')*1000+(hundreds[a][b]-'0' > 30 > 31 int worst = 0; > 32 for(int a=0; a<N; ++a) > 33 for(int b=0; b<N; ++b) { > 34 const int t = d[a][b]; > 35 > 36 vector<int> cand = d[a]; > 37 for(int c=0; c<N; ++c) { > 38 if(b>c && d[a][c]-1>=1) > 39 cand.push_back(d[a][c]-1); > 40 } > 41 cand.push_back(1); > 42 cand.push_back(9999); > 43 for(int i=0; i<cand.size(); ++i) if(1<=cand[i]&&cand[i]< > 44 d[a][b] = cand[i]; > 45 worst = max(worst, goGreedy(d, N)); > 46 } > 47 d[a][b] = t; > 48 } > 49 return worst; > 50 } > 51 > 52 int goGreedy(vector< vector<int> >& d, int N) > 53 { > 54 vector<bool> v(N); > 55 int p = 0; > 56 int total = 0; > 57 for(;;) { > 58 v[p] = true; > 59 vector< pair<int,int> > cand; > 60 for(int q=0; q<N; ++q) > 61 if(!v[q]) > 62 cand.push_back(make_pair(d[p][q],q)); > 63 if(cand.empty()) > 64 return total; > 65 int q = min_element(cand.begin(), cand.end())->second; > 66 total += d[p][q]; > 67 p = q; > 68 } > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, GreedyTravelingSalesman().worstDistance(thousand > 86 int main(){ > 87 > 88 CASE(0) > 89 string thousands_[] = {"055", "505", "550"}; > 90 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 91 string hundreds_[] = {"000", "000", "000"}; > 92 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 93 string tens_[] = {"000", "000", "000"}; > 94 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 95 string ones_[] = {"000", "000", "000"}; > 96 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 97 int _ = 14999; > 98 END > 99 CASE(1) > 100 string thousands_[] = {"018", "101", "990"}; > 101 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 102 string hundreds_[] = {"000", "000", "990"}; > 103 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 104 string tens_[] = {"000", "000", "990"}; > 105 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 106 string ones_[] = {"000", "000", "990"}; > 107 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 108 int _ = 17999; > 109 END > 110 CASE(2) > 111 string thousands_[] = {"00888", "00999", "00099", "00009", "00000"} > 112 ; > 113 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 114 string hundreds_[] = {"00000", "00999", "00099", "00009", "00000"} > 115 ; > 116 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 117 string tens_[] = {"00000", "10999", "11099", "11109", "11110"} > 118 ; > 119 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 120 string ones_[] = {"01000", "00999", "00099", "00009", "00000"} > 121 ; > 122 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 123 int _ = 37997; > 124 END > 125 CASE(3) > 126 string thousands_[] = {"000000", "000000", "990999", "999099", "999909", > 127 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 128 string hundreds_[] = {"000000", "000000", "990999", "999099", "999909", > 129 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 130 string tens_[] = {"000000", "000000", "990999", "999099", "999909", "999 > 131 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 132 string ones_[] = {"011111", "101111", "990998", "999099", "999809", "999 > 133 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 134 int _ = 39994; > 135 END > 136 CASE(4) > 137 string thousands_[] = {"00", "00"}; > 138 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 139 string hundreds_[] = {"00", "00"}; > 140 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 141 string tens_[] = {"00", "00"}; > 142 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 143 string ones_[] = {"01", "10"}; > 144 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 145 int _ = 9999; > 146 END > 147 CASE(5) > 148 string thousands_[] = {"0930", "1064", "0104", "1070"}; > 149 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 150 string hundreds_[] = {"0523", "1062", "6305", "0810"}; > 151 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 152 string tens_[] = {"0913", "0087", "3109", "1500"}; > 153 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 154 string ones_[] = {"0988", "2030", "6103", "5530"}; > 155 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 156 int _ = 14124; > 157 END > 158 CASE(6) > 159 string thousands_[] = {"0329", "2036", "2502", "8970"}; > 160 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 161 string hundreds_[] = {"0860", "5007", "0404", "2770"}; > 162 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 163 string tens_[] = {"0111", "2087", "2009", "2670"}; > 164 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 165 string ones_[] = {"0644", "1094", "7703", "7550"}; > 166 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 167 int _ = 17785; > 168 END > 169 CASE(7) > 170 string thousands_[] = {"098444156277392825243100607342", "20009765683770 > 171 "290231695687128834848596019656", "407026565077650435591867333275", > 172 "843401002617957470339040852874", "349970591997218853400632158696", > 173 "419933000593511123878416328483", "696294503254214847884399055978", > 174 "641473980706392541888675375279", "936720077098054565078142449625", > 175 "203476089500970673371115103717", "511071853860312304204656816567", > 176 "347105714685052402147763392257", "125122220860203856679947732062", > 177 "121462979669220132944063071653", "928254504048223043681383050365", > 178 "502607124708785202536036594373", "793596587517012870906900400361", > 179 "712360060935346182084840996318", "761671392040312345002273366240", > 180 "812935320276738878200716148806", "228506917464479046839069740872", > 181 "755395721473881083093906155745", "192597782177910118061710039501", > 182 "721382839206745793530453013267", "076061794267810491768114700256", > 183 "857528357758085424372388710251", "173322450800442594145600093043", > 184 "761667192345925280210514410800", "521229810525064090301842864060"}; > 185 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 186 string hundreds_[] = {"098270581534726237580246464451", "108829763716747 > 187 "830061279541380758964430491222", "431005058477371114834129826284", > 188 "601807314489142917339949914290", "330640126699733151822328009407", > 189 "851821069798846354566780680271", "648888407535627630663351884365", > 190 "051398660825518466890170447894", "631934884097214069747147155777", > 191 "768071219404930950472885304916", "924954163330715847561718395488", > 192 "189910033179029204426829479070", "960645776060701332402794474433", > 193 "244875842263950931884758650019", "528470075229660077692189442311", > 194 "752198673046476808978058423064", "899325998610605600525587569431", > 195 "965750123741820904031880230236", "121658852172052167706008445728", > 196 "556199378085507717770434101126", "864838242791403197110088834005", > 197 "593435343245223500439707230479", "622529771475840345624500421425", > 198 "503486612623475041392122088159", "518334626169655694269507400008", > 199 "967091631529233593414345370288", "300474162107271438029222620086", > 200 "010527691044447729596127150108", "742822904991333205419603623270"}; > 201 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 202 string tens_[] = {"029421809872798033258029765788", "7051350395697725242 > 203 "170567418260893393020344098265", "401043354947659563658581268242", > 204 "746709065616595245635350557925", "739570024549618413776557843034", > 205 "184597012262496958610853505745", "689811400727818703807051112784", > 206 "894453010121164288965541305235", "323145029073008946088869964941", > 207 "834269564400729646453274750586", "538976762970745472202055589093", > 208 "765511399939087047106252621388", "906733295711605356366138410423", > 209 "107653940551700559321642810836", "428402693021051075533830345295", > 210 "386782660475155103347385287948", "936626025836194580089064628716", > 211 "718522629491464055045890912121", "370656945845300237607868352243", > 212 "951908186614186444840337711498", "535178875249889835014025850038", > 213 "505970047705717604298603983975", "484398304612602344941130624527", > 214 "048342694079170795987835013947", "860331019262176299872846206272", > 215 "549663926438975145562538360932", "329735455392841851511474791078", > 216 "711755200061373546828858448100", "778808866574640894148527759780"}; > 217 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 218 string ones_[] = {"050738147930236727719964251439", "8044925628592823186 > 219 "610197568193830684654773608216", "279000416545607314567843085541", > 220 "782201171759873927350740022455", "043370803444176631019883186675", > 221 "566092086050401228622782761449", "469598907881602996036692882305", > 222 "116923500417992303845370254124", "796876115092839169954790509461", > 223 "783836410405270687557924090071", "095144151150833738671751747749", > 224 "354474585664039135189964700948", "328968176148004939648962631420", > 225 "829651915384290848347221555092", "170980383407813034573738951375", > 226 "728655435703349509419725538350", "121896684176286430427852435647", > 227 "315710894574884960021671476788", "592177839598531202003634382961", > 228 "876587919610157913350259498196", "505517243779897451333006271744", > 229 "618607877753891664471800511372", "826358757330233811836040764274", > 230 "206641252044293046424432092833", "704519364781672964993499009545", > 231 "624793571592392775564426440338", "571938479010503551295729304078", > 232 "077967252884369103891335711508", "870185204806328841827105139840"}; > 233 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 234 int _ = 39896; > 235 END > 236 /* > 237 CASE(8) > 238 string thousands_[] = ; > 239 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 240 string hundreds_[] = ; > 241 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 242 string tens_[] = ; > 243 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 244 string ones_[] = ; > 245 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 246 int _ = ; > 247 END > 248 CASE(9) > 249 string thousands_[] = ; > 250 vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/si > 251 string hundreds_[] = ; > 252 vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof > 253 string tens_[] = ; > 254 vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); > 255 string ones_[] = ; > 256 vector <string> ones(ones_, ones_+sizeof(ones_)/sizeof(*ones_)); > 257 int _ = ; > 258 END > 259 */ > 260 } > 261 // END CUT HERE
Added SRM/TCO12-2C-U/1B.cpp version [c0de4a8f67dfbf76]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <memory> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef long double LD; > 21 typedef complex<LD> CMP; > 22 > 23 template<typename T=LL> > 24 struct FenwickTree > 25 { > 26 vector<T> x; > 27 FenwickTree(size_t n) : x(n) {} > 28 > 29 void incr( int k, const T& a ) { // z[k] += a; > 30 for(; k < x.size(); k|=k+1) > 31 x[k] += a; > 32 } > 33 T sum(int i, int j) { // Sigma z[i,j) excl. > 34 return sum_impl(j-1) - sum_impl(i-1); > 35 } > 36 T sum_impl(int j) { // Sigma z[0,j] incl. > 37 T v = T(); > 38 for(; j>=0; j=(j&(j+1))-1) > 39 v += x[j]; > 40 return v; > 41 } > 42 }; > 43 > 44 template<typename T> > 45 std::vector<int> compress(std::vector<T>& xs) > 46 { > 47 std::vector< pair<T,int> > xi; > 48 for(int i=0; i<xs.size(); ++i) > 49 xi.push_back( make_pair(xs[i], i) ); > 50 sort(xi.begin(), xi.end()); > 51 > 52 std::vector<int> result(xs.size()); > 53 for(int k=0; k<xi.size(); ++k) > 54 result[xi[k].second] = k; > 55 return result; > 56 } > 57 > 58 class ThreePoints { public: > 59 long long countColoring(int N, > 60 int xzero, int xmul, int xadd, int xmod, > 61 int yzero, int ymul, int yadd, int ymod) > 62 { > 63 vector<int> x(N), y(N); > 64 x[0] = xzero; for(int i=1; i<N; ++i) x[i] = (x[i-1] * LL(xmul) + > 65 y[0] = yzero; for(int i=1; i<N; ++i) y[i] = (y[i-1] * LL(ymul) + > 66 x = compress(x); > 67 y = compress(y); > 68 > 69 vector< pair<int,int> > y_desc; > 70 for(int i=0; i<N; ++i) > 71 y_desc.push_back(make_pair(y[i], x[i])); > 72 sort(y_desc.rbegin(), y_desc.rend()); > 73 > 74 LL result = 0; > 75 FenwickTree<> p(N), sp(N); > 76 for(int i=0; i<N; ++i) { > 77 const int x = y_desc[i].second; > 78 LL sp_ = p.sum(x+1, N); > 79 LL ssp_ = sp.sum(x+1, N); > 80 p.incr(x, 1); > 81 sp.incr(x, sp_); > 82 result += sp_*(sp_-1)/2 - ssp_; > 83 } > 84 return result; > 85 } > 86 }; > 87 > 88 // BEGIN CUT HERE > 89 #include <ctime> > 90 double start_time; string timer() > 91 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 92 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 93 { os << "{ "; > 94 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 95 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 96 void verify_case(const long long& Expected, const long long& Received) { > 97 bool ok = (Expected == Received); > 98 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 99 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 100 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 101 #define END verify_case(_, ThreePoints().countColoring(N, xzero, xmul, xadd > 102 int main(){ > 103 > 104 CASE(0) > 105 int N = 9; > 106 int xzero = 3; > 107 int xmul = 8; > 108 int xadd = 6; > 109 int xmod = 11; > 110 int yzero = 5; > 111 int ymul = 7; > 112 int yadd = 8; > 113 int ymod = 11; > 114 long long _ = 8LL; > 115 END > 116 CASE(1) > 117 int N = 4; > 118 int xzero = 9; > 119 int xmul = 6; > 120 int xadd = 8; > 121 int xmod = 10; > 122 int yzero = 4; > 123 int ymul = 8; > 124 int yadd = 5; > 125 int ymod = 10; > 126 long long _ = 2LL; > 127 END > 128 CASE(2) > 129 int N = 20; > 130 int xzero = 30; > 131 int xmul = 3; > 132 int xadd = 71; > 133 int xmod = 100; > 134 int yzero = 78; > 135 int ymul = 12; > 136 int yadd = 50; > 137 int ymod = 100; > 138 long long _ = 263LL; > 139 END > 140 CASE(3) > 141 int N = 300000; > 142 int xzero = 99097861; > 143 int xmul = 102766912; > 144 int xadd = 95284952; > 145 int xmod = 123456789; > 146 int yzero = 443104491; > 147 int ymul = 971853214; > 148 int yadd = 569775557; > 149 int ymod = 987654321; > 150 long long _ = 749410681185726LL; > 151 END > 152 /* > 153 CASE(4) > 154 int N = ; > 155 int xzero = ; > 156 int xmul = ; > 157 int xadd = ; > 158 int xmod = ; > 159 int yzero = ; > 160 int ymul = ; > 161 int yadd = ; > 162 int ymod = ; > 163 long long _ = LL; > 164 END > 165 CASE(5) > 166 int N = ; > 167 int xzero = ; > 168 int xmul = ; > 169 int xadd = ; > 170 int xmod = ; > 171 int yzero = ; > 172 int ymul = ; > 173 int yadd = ; > 174 int ymod = ; > 175 long long _ = LL; > 176 END > 177 */ > 178 } > 179 // END CUT HERE
Modified lib/dataStructure/fenwickTree.cpp from [5a7c5bc1ec0fdf30] to [0057b5a349c30181].
1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // Fenwick Tree 2 // Fenwick Tree 3 // O(log N) per each operation 3 // O(log N) per each operation 4 // 4 // 5 // Verified by 5 // Verified by 6 // - SRM424 Div1 LV3 6 // - SRM424 Div1 LV3 > 7 // - TCO12 R2C LV2 7 //------------------------------------------------------------- 8 //------------------------------------------------------------- 8 9 9 template<typename T = LL> | 10 template<typename T=LL> 10 struct FenwickTree 11 struct FenwickTree 11 { 12 { 12 vector<T> x; 13 vector<T> x; 13 FenwickTree(size_t n, const T& v = T()) : x(n, v) {} | 14 FenwickTree(size_t n) : x(n) {} 14 15 15 void incr( int k, const T& a ) { // z[k] += a; 16 void incr( int k, const T& a ) { // z[k] += a; 16 for(; k < x.size(); k|=k+1) 17 for(; k < x.size(); k|=k+1) 17 x[k] += a; 18 x[k] += a; 18 } 19 } > 20 T sum(int i, int j) { // Sigma z[i,j) excl. > 21 return sum_impl(j-1) - sum_impl(i-1); 19 | 22 } 20 T sum(int i, int j) { // z[i]+...+z[j] : inclusive < 21 if(i) < 22 return sum(0, j) - sum(0, i-1); | 23 T sum_impl(int j) { // Sigma z[0,j] incl. 23 else { < 24 T v = T(); | 24 T v = T(); 25 for(; j>=0; j=(j&(j+1))-1) | 25 for(; j>=0; j=(j&(j+1))-1) 26 v += x[j]; | 26 v += x[j]; 27 return v; | 27 return v; 28 } < 29 } 28 } 30 }; 29 };
Modified lib/dataStructure/segmentTree.cpp from [0226be12935bcdf4] to [f9b609a5f0b95ebf].
24 while(N>>=1) { 24 while(N>>=1) { 25 tree.resize(tree.size()+1); tree.back().resize(N); 25 tree.resize(tree.size()+1); tree.back().resize(N); 26 for(int i=0; i<N; ++i) 26 for(int i=0; i<N; ++i) 27 CalcMidNode(tree.size()-1, i); 27 CalcMidNode(tree.size()-1, i); 28 } 28 } 29 } 29 } 30 30 31 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) | 31 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 33 } 33 } 34 34 35 template<typename Value> 35 template<typename Value> 36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log nE|e-s|) | 36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|) 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 38 } 38 } 39 39 40 private: 40 private: 41 void CalcMidNode(int lv, int idx) 41 void CalcMidNode(int lv, int idx) 42 { 42 { 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2
Added lib/typical/coordinate_compression.cpp version [5adf500ce372739d]
> 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 > 4 > 5 template<typename T> > 6 std::vector<int> compress(std::vector<T>& xs) > 7 { > 8 std::vector< pair<T,int> > xi; > 9 for(int i=0; i<xs.size(); ++i) > 10 xi.push_back( make_pair(xs[i], i) ); > 11 sort(xi.begin(), xi.end()); > 12 > 13 std::vector<int> result(xs.size()); > 14 for(int k=0; k<xi.size(); ++k) > 15 result[xi[k].second] = k; > 16 return result; > 17 }