Overview
| SHA1 Hash: | 2034908d41c01074ba2be41f9baf0b8829c7db67 |
|---|---|
| Date: | 2012-05-20 14:16:51 |
| User: | kinaba |
| Comment: | 543 |
| 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/543/1A.cpp version [7b0052037b97ced1]
> 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 <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class EllysXors { public: > 29 long long getXor(long long L, long long R) > 30 { > 31 if( R-L < 5 ) { > 32 LL a = 0; > 33 for(LL v=L; v<=R; ++v) > 34 a ^= v; > 35 return a; > 36 } > 37 > 38 LL a = 0; > 39 if( L%2 == 1 ) { > 40 a ^= L; > 41 ++L; > 42 } > 43 if( R%2 == 0 ) { > 44 a ^= R; > 45 --R; > 46 } > 47 return a ^ ((R+1-L)/2%2); > 48 } > 49 }; > 50 > 51 // BEGIN CUT HERE > 52 #include <ctime> > 53 double start_time; string timer() > 54 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 55 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 56 { os << "{ "; > 57 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 58 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 59 void verify_case(const long long& Expected, const long long& Received) { > 60 bool ok = (Expected == Received); > 61 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 62 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 63 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 64 #define END verify_case(_, EllysXors().getXor(L, R));} > 65 int main(){ > 66 > 67 CASE(0) > 68 long long L = 3LL; > 69 long long R = 10LL; > 70 long long _ = 8LL; > 71 END > 72 CASE(1) > 73 long long L = 5LL; > 74 long long R = 5LL; > 75 long long _ = 5LL; > 76 END > 77 CASE(2) > 78 long long L = 13LL; > 79 long long R = 42LL; > 80 long long _ = 39LL; > 81 END > 82 CASE(3) > 83 long long L = 666LL; > 84 long long R = 1337LL; > 85 long long _ = 0LL; > 86 END > 87 CASE(4) > 88 long long L = 1234567LL; > 89 long long R = 89101112LL; > 90 long long _ = 89998783LL; > 91 END > 92 /* > 93 CASE(5) > 94 long long L = LL; > 95 long long R = LL; > 96 long long _ = LL; > 97 END > 98 CASE(6) > 99 long long L = LL; > 100 long long R = LL; > 101 long long _ = LL; > 102 END > 103 */ > 104 } > 105 // END CUT HERE
Added SRM/543/1B.cpp version [d73b3908d1719487]
> 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 template<typename T> > 23 struct DP2x > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2x(int, int N2, const T& t = T()) > 28 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( > 29 T& operator()(int i1, int i2) > 30 { i1&=1; return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2x& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 class EllysRivers { public: > 36 double getMin(int length, int walk, vector <int> width, vector <int> spe > 37 { > 38 DP2x<LD> dp(width.size()+1, length+1); > 39 for(int x=0; x<=length; ++x) > 40 dp(0,x) = x / LD(walk); > 41 > 42 for(int y=1; y<=width.size(); ++y) { > 43 LD w = width[y-1]; > 44 LD s = speed[y-1]; > 45 > 46 for(int x=length,px=length; x>=0; --x) { > 47 retry: > 48 LD t = dp(y-1, px) + sqrt(LD(px-x)*(px-x) + w*w) > 49 if( px > 0 ) { > 50 LD tt = dp(y-1, px-1) + sqrt(LD(px-1-x)* > 51 if( tt < t ) { > 52 --px; > 53 goto retry; > 54 } > 55 } > 56 dp(y, x) = t; > 57 } > 58 } > 59 > 60 return dp(width.size(), length); > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 LD start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const LD& Expected, const LD& Received) { > 73 bool ok = (abs(Expected - Received) < 1e-9); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, EllysRivers().getMin(length, walk, width, speed) > 78 int main(){ > 79 > 80 CASE(0) > 81 int length = 10; > 82 int walk = 3; > 83 int width_[] = {5, 2, 3}; > 84 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 85 int speed_[] = {5, 2, 7}; > 86 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 87 LD _ = 3.231651964071508; > 88 END > 89 CASE(1) > 90 int length = 10000; > 91 int walk = 211; > 92 int width_[] = {911}; > 93 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 94 int speed_[] = {207}; > 95 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 96 LD _ = 48.24623664712219; > 97 END > 98 CASE(2) > 99 int length = 1337; > 100 int walk = 2; > 101 int width_[] = {100, 200, 300, 400}; > 102 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 103 int speed_[] = {11, 12, 13, 14}; > 104 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 105 LD _ = 128.57830549575695; > 106 END > 107 CASE(3) > 108 int length = 77; > 109 int walk = 119; > 110 int width_[] = {11, 12, 13, 14}; > 111 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 112 int speed_[] = {100, 200, 300, 400}; > 113 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 114 LD _ = 0.3842077071089629; > 115 END > 116 CASE(4) > 117 int length = 7134; > 118 int walk = 1525; > 119 int width_[] = {11567, 19763, 11026, 10444, 24588, 22263, 17709, 11181, > 120 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 121 int speed_[] = {1620, 1477, 2837, 2590, 1692, 2270, 1655, 1078, 2683, 14 > 122 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 123 LD _ = 214.6509731258811; > 124 END > 125 CASE(5) > 126 int length = 100000; > 127 int walk = 1; > 128 int width_[] = {1000000, 1000000, 1000000}; > 129 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 130 int speed_[] = {1, 1000000, 1}; > 131 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 132 LD _ = 2000001.004987562; > 133 END > 134 CASE(6) > 135 int length = 100000; > 136 int walk = 1; > 137 int width_[] = {1000000, 1000000, 1000000}; > 138 vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); > 139 int speed_[] = {1000000, 1000000, 1}; > 140 vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); > 141 LD _ = 1000002.0024984397; > 142 END > 143 } > 144 // END CUT HERE
Added SRM/543/1C.cpp version [978635090b60953d]
> 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 struct Ship { > 23 CMP s, e; > 24 LD speed; > 25 LD r; > 26 LD energy; > 27 }; > 28 > 29 template<typename T> > 30 class IdGen > 31 { > 32 map<T, int> v2id_; > 33 vector<T> id2v_; > 34 public: > 35 int v2id(const T& v) { > 36 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 37 return v2id_[v]; > 38 } > 39 const T& id2v(int i) const { return id2v_[i]; } > 40 int size() const { return id2v_.size(); } > 41 }; > 42 > 43 template<typename Vert, typename Flow, int NV=512> > 44 class MaxFlow > 45 { > 46 IdGen<Vert> idgen; > 47 vector<int> G[NV]; > 48 Flow F[NV][NV]; > 49 > 50 public: > 51 void addEdge( Vert s_, Vert t_, Flow f ) > 52 { > 53 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 54 G[s].push_back(t); > 55 G[t].push_back(s); > 56 F[s][t] = f; > 57 F[t][s] = 0; > 58 } > 59 > 60 Flow calc( Vert s_, Vert t_ ) > 61 { > 62 const int S = idgen.v2id(s_), D = idgen.v2id(t_); > 63 for( Flow total=0 ;; ) { > 64 // Do BFS and compute the level for each node. > 65 int LV[NV] = {0}; > 66 vector<int> Q(1, S); > 67 for(int lv=1; !Q.empty(); ++lv) { > 68 vector<int> Q2; > 69 for(size_t i=0; i!=Q.size(); ++i) { > 70 const vector<int>& ne = G[Q[i]]; > 71 for(size_t j=0; j!=ne.size(); ++j) > 72 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 73 LV[ne[j]]=lv, Q2.push_ba > 74 } > 75 Q.swap(Q2); > 76 } > 77 > 78 // Destination is now unreachable. Done. > 79 if( !LV[D] ) > 80 return total; > 81 > 82 // Iterating DFS. > 83 bool blocked[NV] = {}; > 84 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 85 } > 86 } > 87 > 88 private: > 89 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 90 { > 91 Flow flow_out = 0; > 92 for(size_t i=0; i!=G[v].size(); ++i) { > 93 int u = G[v][i]; > 94 if( LV[v]+1==LV[u] && F[v][u] ) { > 95 Flow f = min(flow_in-flow_out, F[v][u]); > 96 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 97 F[v][u] -= f; > 98 F[u][v] += f; > 99 flow_out += f; > 100 if( flow_in == flow_out ) return flow_ou > 101 } > 102 } > 103 } > 104 blocked[v] = (flow_out==0); > 105 return flow_out; > 106 } > 107 }; > 108 > 109 bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2) > 110 { > 111 CMP v = (lb-la) / abs(lb-la); > 112 CMP o = (c-la) / v; > 113 if( abs(o.imag()) > r ) > 114 return false; > 115 LD dx = sqrt(r*r - o.imag()*o.imag()); > 116 *p1 = la + (o.real()-dx)*v; > 117 *p2 = la + (o.real()+dx)*v; > 118 return true; > 119 } > 120 > 121 class EllysDeathStars { public: > 122 double getMax(vector <string> stars_, vector <string> ships_) > 123 { > 124 vector<CMP> stars; > 125 for(int i=0; i<stars_.size(); ++i) > 126 { > 127 stringstream sin(stars_[i]); > 128 int x, y; > 129 sin >> x >> y; > 130 stars.push_back(CMP(x,y)); > 131 } > 132 vector<Ship> ships; > 133 for(int i=0; i<ships_.size(); ++i) > 134 { > 135 stringstream sin(ships_[i]); > 136 int sx, sy, ex, ey, s, r, e; > 137 sin >> sx >> sy >> ex >> ey >> s >> r >> e; > 138 Ship ship; > 139 ship.s = CMP(sx,sy); > 140 ship.e = CMP(ex,ey); > 141 if(ship.s == ship.e) > 142 continue; > 143 ship.speed = s; > 144 ship.r = r; > 145 ship.energy = e; > 146 ships.push_back(ship); > 147 } > 148 return solve(stars, ships); > 149 } > 150 > 151 LD solve(const vector<CMP>& stars, const vector<Ship>& ships) > 152 { > 153 typedef pair<int, int> Vert; > 154 MaxFlow<Vert, LD, 2048>* mf = new MaxFlow<Vert, LD, 2048>(); > 155 for(int b=0; b<ships.size(); ++b) > 156 mf->addEdge(Vert(0,0), Vert(1,b), ships[b].energy); > 157 > 158 int id = 0; > 159 for(int a=0; a<stars.size(); ++a) { > 160 vector<LD> events; > 161 events.push_back(0); > 162 for(int b=0; b<ships.size(); ++b) > 163 events.push_back(abs(ships[b].e-ships[b].s) / sh > 164 LD lasttime = *max_element(events.begin(), events.end()) > 165 > 166 for(int b=0; b<ships.size(); ++b) { > 167 CMP p = ships[b].s; > 168 CMP q = ships[b].e; > 169 CMP o = stars[a]; > 170 LD r = ships[b].r; > 171 LD speed = ships[b].speed; > 172 > 173 o = (o - p) / ((q-p) / abs(q-p)); > 174 LD y = abs(o.imag()); > 175 if( y < r ) { > 176 LD dx = sqrt(r*r - y*y); > 177 LD x1 = o.real() - dx; > 178 LD x2 = o.real() + dx; > 179 if(0<x1/speed && x1/speed<lasttime) > 180 events.push_back( x1 / speed ); > 181 if(0<x2/speed && x2/speed<lasttime) > 182 events.push_back( x2 / speed ); > 183 } > 184 } > 185 sort(events.begin(), events.end()); > 186 > 187 for(int i=0; i+1<events.size(); ++i, ++id) { > 188 LD sec = events[i+1] - events[i]; > 189 LD mid = (events[i+1] + events[i]) / 2; > 190 for(int b=0; b<ships.size(); ++b) { > 191 LD rng = abs(ships[b].e - ships[b].s) / > 192 CMP pos = ships[b].s + (ships[b].e-ships > 193 if( 0<mid && mid<rng && abs(pos-stars[a] > 194 mf->addEdge(Vert(1,b), Vert(2,id > 195 } > 196 mf->addEdge(Vert(2,id), Vert(3,0), sec); > 197 } > 198 } > 199 > 200 LD flow = mf->calc(Vert(0,0), Vert(3,0)); > 201 delete mf; > 202 return flow; > 203 } > 204 }; > 205 > 206 // BEGIN CUT HERE > 207 #include <ctime> > 208 LD start_time; string timer() > 209 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 210 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 211 { os << "{ "; > 212 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 213 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 214 void verify_case(const LD& Expected, const LD& Received) { > 215 bool ok = (abs(Expected - Received) < 1e-9); > 216 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 217 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 218 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 219 #define END verify_case(_, EllysDeathStars().getMax(stars, ships));} > 220 int main(){ > 221 > 222 CASE(0) > 223 string stars_[] = {"2 2"}; > 224 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 225 string ships_[] = {"1 1 5 3 2 1 2"}; > 226 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 227 LD _ = 0.894427190999916; > 228 END > 229 CASE(1) > 230 string stars_[] = {"12 10", "7 5"}; > 231 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 232 string ships_[] = {"10 10 12 10 1 1 3", "6 1 8 10 1 2 3", "3 6 8 2 5 3 1 > 233 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 234 LD _ = 4.983770744659944; > 235 END > 236 CASE(2) > 237 string stars_[] = {"5 77", "60 50", "10 46", "22 97", "87 69"}; > 238 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 239 string ships_[] = {"42 17 66 11 5 7 13", "10 10 20 20 3 3 3", "13 15 18 > 240 "99 71 63 81 19 4 60", "27 34 56 43 11 3 12"}; > 241 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 242 LD _ = 0.0; > 243 END > 244 CASE(3) > 245 string stars_[] = {"141 393", "834 847", "568 43", "18 228", "515 794", > 246 "167 283", "849 333", "719 738", "434 261", "613 800", > 247 "127 340", "466 938", "598 601"}; > 248 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 249 string ships_[] = {"410 951 472 100 337 226 210", "713 352 677 908 731 6 > 250 "191 41 337 92 446 716 213", "598 889 446 907 148 650 203", > 251 "168 556 470 924 344 369 198", "300 182 350 936 737 533 45", > 252 "410 871 488 703 746 631 80", "270 777 636 539 172 103 56", > 253 "466 906 522 98 693 77 309", "768 698 846 110 14 643 14", > 254 "755 724 664 465 263 759 120"}; > 255 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 256 LD _ = 31.965770956316362; > 257 END > 258 CASE(4) > 259 string stars_[] = > 260 {"20 1", "70 1", "120 1", "170 1", "220 1", "270 1", "320 1", "370 1", "420 1", > 261 ; > 262 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 263 string ships_[] = > 264 {"1 21 1000 21 1 21 257", "1 20 1000 20 1 21 102", "1 19 1000 19 > 265 ; > 266 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 267 LD _ = 837.0709015727234; > 268 END > 269 CASE(5) > 270 string stars_[] = {"8 7", "11 9"}; > 271 vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); > 272 string ships_[] = {"11 14 8 10 92 3 3", "12 14 12 6 434 4 6"}; > 273 vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); > 274 LD _ = 0.01583636715715995; > 275 END > 276 } > 277 // END CUT HERE
Modified TZTesterSp/template.cpp from [56e8b77f261a915b] to [6e30a998ce576012].
10 #include <iterator> 10 #include <iterator> 11 #include <functional> 11 #include <functional> 12 #include <complex> 12 #include <complex> 13 #include <queue> 13 #include <queue> 14 #include <stack> 14 #include <stack> 15 #include <cmath> 15 #include <cmath> 16 #include <cassert> 16 #include <cassert> 17 #include <cstring> < 18 #ifdef __GNUC__ < 19 #include <ext/hash_map> < 20 #define unordered_map __gnu_cxx::hash_map < 21 #else < 22 #include <unordered_map> < 23 #endif < 24 using namespace std; 17 using namespace std; 25 typedef long long LL; 18 typedef long long LL; > 19 typedef long double LD; 26 typedef complex<double> CMP; | 20 typedef complex<LD> CMP; 27 21 28 class $CLASSNAME$ { public: 22 class $CLASSNAME$ { public: 29 $RC$ $METHODNAME$($METHODPARMS$) 23 $RC$ $METHODNAME$($METHODPARMS$) 30 { 24 { 31 } 25 } 32 }; 26 }; 33 27 34 $TESTCODE$ 28 $TESTCODE$
Added lib/geo/line_circle.cpp version [0f1f35288c2dfafe]
> 1 typedef long double LD; > 2 typedef complex<LD> CMP; > 3 > 4 bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2) > 5 { > 6 CMP v = (lb-la) / abs(lb-la); > 7 CMP o = (c-la) / v; > 8 if( abs(o.imag()) > r ) > 9 return false; > 10 LD dx = sqrt(r*r - o.imag()*o.imag()); > 11 *p1 = la + (o.real()-dx)*v; > 12 *p2 = la + (o.real()+dx)*v; > 13 return true; > 14 }
Modified lib/graph/maxFlow.cpp from [296b9275312ebbf1] to [6a23b64e61d31ffb].
7 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 7 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 8 // 8 // 9 // Verified by 9 // Verified by 10 // - SRM 399 Div1 LV3 10 // - SRM 399 Div1 LV3 11 // - PKU 1459 11 // - PKU 1459 12 // - CodeCraft 09 CUTS 12 // - CodeCraft 09 CUTS 13 // - SRM 465 Div1 LV2 13 // - SRM 465 Div1 LV2 > 14 // - SRM 543 Div1 LV3 14 //------------------------------------------------------------- 15 //------------------------------------------------------------- 15 16 16 template<typename T> 17 template<typename T> 17 class IdGen 18 class IdGen 18 { 19 { 19 map<T, int> v2id_; 20 map<T, int> v2id_; 20 vector<T> id2v_; 21 vector<T> id2v_;