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, vector <string> tens, vector <string> ones) 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')*100+(tens[a][b]-'0')*10+(ones[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]<=9999){ 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 83 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 84 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 85 +#define END verify_case(_, GreedyTravelingSalesman().worstDistance(thousands, hundreds, tens, ones));} 86 +int main(){ 87 + 88 +CASE(0) 89 + string thousands_[] = {"055", "505", "550"}; 90 + vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 91 + string hundreds_[] = {"000", "000", "000"}; 92 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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_)/sizeof(*thousands_)); 102 + string hundreds_[] = {"000", "000", "990"}; 103 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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_)/sizeof(*thousands_)); 114 + string hundreds_[] = {"00000", "00999", "00099", "00009", "00000"} 115 +; 116 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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", "999990"}; 127 + vector <string> thousands(thousands_, thousands_+sizeof(thousands_)/sizeof(*thousands_)); 128 + string hundreds_[] = {"000000", "000000", "990999", "999099", "999909", "999990"}; 129 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 130 + string tens_[] = {"000000", "000000", "990999", "999099", "999909", "999990"}; 131 + vector <string> tens(tens_, tens_+sizeof(tens_)/sizeof(*tens_)); 132 + string ones_[] = {"011111", "101111", "990998", "999099", "999809", "999980"}; 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_)/sizeof(*thousands_)); 139 + string hundreds_[] = {"00", "00"}; 140 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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_)/sizeof(*thousands_)); 150 + string hundreds_[] = {"0523", "1062", "6305", "0810"}; 151 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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_)/sizeof(*thousands_)); 161 + string hundreds_[] = {"0860", "5007", "0404", "2770"}; 162 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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", "200097656837707947798866622385", 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_)/sizeof(*thousands_)); 186 + string hundreds_[] = {"098270581534726237580246464451", "108829763716747148395013332067", 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(*hundreds_)); 202 + string tens_[] = {"029421809872798033258029765788", "705135039569772524273274786652", 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", "804492562859282318664226330103", 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_)/sizeof(*thousands_)); 240 + string hundreds_[] = ; 241 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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_)/sizeof(*thousands_)); 251 + string hundreds_[] = ; 252 + vector <string> hundreds(hundreds_, hundreds_+sizeof(hundreds_)/sizeof(*hundreds_)); 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) + xadd) % xmod; 65 + y[0] = yzero; for(int i=1; i<N; ++i) y[i] = (y[i-1] * LL(ymul) + yadd) % ymod; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 99 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 100 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 101 +#define END verify_case(_, ThreePoints().countColoring(N, xzero, xmul, xadd, xmod, yzero, ymul, yadd, ymod));} 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 2 // Fenwick Tree 3 3 // O(log N) per each operation 4 4 // 5 5 // Verified by 6 6 // - SRM424 Div1 LV3 7 +// - TCO12 R2C LV2 7 8 //------------------------------------------------------------- 8 9 9 -template<typename T = LL> 10 +template<typename T=LL> 10 11 struct FenwickTree 11 12 { 12 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 16 void incr( int k, const T& a ) { // z[k] += a; 16 17 for(; k < x.size(); k|=k+1) 17 18 x[k] += a; 18 19 } 19 - 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 - else { 24 - T v = T(); 25 - for(; j>=0; j=(j&(j+1))-1) 26 - v += x[j]; 27 - return v; 28 - } 20 + T sum(int i, int j) { // Sigma z[i,j) excl. 21 + return sum_impl(j-1) - sum_impl(i-1); 22 + } 23 + T sum_impl(int j) { // Sigma z[0,j] incl. 24 + T v = T(); 25 + for(; j>=0; j=(j&(j+1))-1) 26 + v += x[j]; 27 + return v; 29 28 } 30 29 };
Modified lib/dataStructure/segmentTree.cpp from [0226be12935bcdf4] to [f9b609a5f0b95ebf].
24 24 while(N>>=1) { 25 25 tree.resize(tree.size()+1); tree.back().resize(N); 26 26 for(int i=0; i<N; ++i) 27 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 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 33 33 } 34 34 35 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 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 38 38 } 39 39 40 40 private: 41 41 void CalcMidNode(int lv, int idx) 42 42 { 43 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
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 +}