Artifact 60ffa78d3698d241174c659aa047a730ec7a2cbe:
0000: 2f 2f 20 43 6f 6e 76 65 72 74 20 61 20 6c 69 73 // Convert a lis
0010: 74 20 6f 66 20 4e 20 65 6c 65 6d 65 6e 74 73 20 t of N elements
0020: 77 69 74 68 20 4b 20 64 69 73 74 69 6e 63 74 20 with K distinct
0030: 65 6c 65 6d 65 6e 74 73 20 74 6f 20 5b 6f 72 69 elements to [ori
0040: 67 69 6e 20 2e 2e 20 6f 72 69 67 69 6e 2b 4b 29 gin .. origin+K)
0050: 2c 0a 2f 2f 20 70 72 65 73 65 72 76 69 6e 67 20 ,.// preserving
0060: 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 6f 72 64 the original ord
0070: 65 72 2e 20 20 4f 28 4e 20 6c 6f 67 20 4e 29 2c er. O(N log N),
0080: 20 62 75 74 20 64 6f 65 73 6e 27 74 20 69 6e 63 but doesn't inc
0090: 75 72 20 74 68 65 20 6f 76 65 72 68 65 61 64 20 ur the overhead
00a0: 6f 66 20 73 74 64 3a 3a 6d 61 70 2e 0a 2f 2f 20 of std::map..//
00b0: 54 65 73 74 65 64 3a 20 54 43 4f 20 32 30 31 32 Tested: TCO 2012
00c0: 20 52 32 43 20 4d 69 64 2c 20 53 52 4d 20 35 38 R2C Mid, SRM 58
00d0: 34 20 4d 69 64 0a 0a 74 65 6d 70 6c 61 74 65 3c 4 Mid..template<
00e0: 74 79 70 65 6e 61 6d 65 20 54 3e 0a 76 65 63 74 typename T>.vect
00f0: 6f 72 3c 69 6e 74 3e 20 63 6f 6d 70 72 65 73 73 or<int> compress
0100: 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e (const vector<T>
0110: 26 20 78 73 2c 20 69 6e 74 20 6f 72 69 67 69 6e & xs, int origin
0120: 20 3d 20 30 29 0a 7b 0a 09 76 65 63 74 6f 72 3c = 0).{..vector<
0130: 20 70 61 69 72 3c 54 2c 69 6e 74 3e 20 3e 20 78 pair<T,int> > x
0140: 69 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b i;..for(int i=0;
0150: 20 69 3c 78 73 2e 73 69 7a 65 28 29 3b 20 2b 2b i<xs.size(); ++
0160: 69 29 0a 09 09 78 69 2e 70 75 73 68 5f 62 61 63 i)...xi.push_bac
0170: 6b 28 20 6d 61 6b 65 5f 70 61 69 72 28 78 73 5b k( make_pair(xs[
0180: 69 5d 2c 20 69 29 20 29 3b 0a 09 73 6f 72 74 28 i], i) );..sort(
0190: 78 69 2e 62 65 67 69 6e 28 29 2c 20 78 69 2e 65 xi.begin(), xi.e
01a0: 6e 64 28 29 29 3b 0a 0a 09 76 65 63 74 6f 72 3c nd());...vector<
01b0: 69 6e 74 3e 20 72 65 73 75 6c 74 28 78 73 2e 73 int> result(xs.s
01c0: 69 7a 65 28 29 29 3b 0a 09 66 6f 72 28 69 6e 74 ize());..for(int
01d0: 20 6b 3d 30 2c 69 64 3d 6f 72 69 67 69 6e 3b 20 k=0,id=origin;
01e0: 6b 3c 78 69 2e 73 69 7a 65 28 29 3b 20 2b 2b 6b k<xi.size(); ++k
01f0: 29 20 7b 0a 09 09 69 66 28 30 3c 3d 6b 2d 31 20 ) {...if(0<=k-1
0200: 26 26 20 78 69 5b 6b 2d 31 5d 2e 66 69 72 73 74 && xi[k-1].first
0210: 3c 78 69 5b 6b 5d 2e 66 69 72 73 74 29 0a 09 09 <xi[k].first)...
0220: 09 2b 2b 69 64 3b 0a 09 09 72 65 73 75 6c 74 5b .++id;...result[
0230: 78 69 5b 6b 5d 2e 73 65 63 6f 6e 64 5d 20 3d 20 xi[k].second] =
0240: 69 64 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 72 id;..}..return r
0250: 65 73 75 6c 74 3b 0a 7d 0a esult;.}.