Artifact 5adf500ce372739d7e7224492a70a6efbed053dd:
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 64 69 73 74 69 6e 63 74 20 65 6c t of distinct el
0020: 65 6d 65 6e 74 73 20 74 6f 20 5b 30 2e 2e 4e 29 ements to [0..N)
0030: 2c 20 70 72 65 73 65 72 76 69 6e 67 20 74 68 65 , preserving the
0040: 20 6f 72 69 67 69 6e 61 6c 20 6f 72 64 65 72 2e original order.
0050: 0a 2f 2f 20 4f 28 4e 20 6c 6f 67 20 4e 29 2c 20 .// O(N log N),
0060: 62 75 74 20 64 6f 65 73 6e 27 74 20 69 6e 63 75 but doesn't incu
0070: 72 20 74 68 65 20 6f 76 65 72 68 65 61 64 20 6f r the overhead o
0080: 66 20 73 74 64 3a 3a 6d 61 70 2e 0a 2f 2f 20 54 f std::map..// T
0090: 65 73 74 65 64 3a 20 54 43 4f 20 32 30 31 32 20 ested: TCO 2012
00a0: 52 32 43 20 4d 69 64 0a 0a 74 65 6d 70 6c 61 74 R2C Mid..templat
00b0: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a 73 74 e<typename T>.st
00c0: 64 3a 3a 76 65 63 74 6f 72 3c 69 6e 74 3e 20 63 d::vector<int> c
00d0: 6f 6d 70 72 65 73 73 28 73 74 64 3a 3a 76 65 63 ompress(std::vec
00e0: 74 6f 72 3c 54 3e 26 20 78 73 29 0a 7b 0a 09 73 tor<T>& xs).{..s
00f0: 74 64 3a 3a 76 65 63 74 6f 72 3c 20 70 61 69 72 td::vector< pair
0100: 3c 54 2c 69 6e 74 3e 20 3e 20 78 69 3b 0a 09 66 <T,int> > xi;..f
0110: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 78 73 or(int i=0; i<xs
0120: 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 09 .size(); ++i)...
0130: 78 69 2e 70 75 73 68 5f 62 61 63 6b 28 20 6d 61 xi.push_back( ma
0140: 6b 65 5f 70 61 69 72 28 78 73 5b 69 5d 2c 20 69 ke_pair(xs[i], i
0150: 29 20 29 3b 0a 09 73 6f 72 74 28 78 69 2e 62 65 ) );..sort(xi.be
0160: 67 69 6e 28 29 2c 20 78 69 2e 65 6e 64 28 29 29 gin(), xi.end())
0170: 3b 0a 0a 09 73 74 64 3a 3a 76 65 63 74 6f 72 3c ;...std::vector<
0180: 69 6e 74 3e 20 72 65 73 75 6c 74 28 78 73 2e 73 int> result(xs.s
0190: 69 7a 65 28 29 29 3b 0a 09 66 6f 72 28 69 6e 74 ize());..for(int
01a0: 20 6b 3d 30 3b 20 6b 3c 78 69 2e 73 69 7a 65 28 k=0; k<xi.size(
01b0: 29 3b 20 2b 2b 6b 29 0a 09 09 72 65 73 75 6c 74 ); ++k)...result
01c0: 5b 78 69 5b 6b 5d 2e 73 65 63 6f 6e 64 5d 20 3d [xi[k].second] =
01d0: 20 6b 3b 0a 09 72 65 74 75 72 6e 20 72 65 73 75 k;..return resu
01e0: 6c 74 3b 0a 7d 0a lt;.}.