Overview
| SHA1 Hash: | db58c713f60bc32242e462976d229791dfe7d4dc |
|---|---|
| Date: | 2012-02-24 12:44:38 |
| User: | kinaba |
| Comment: | 534 |
| 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/532-U/2A.cpp version [1bee238b07757020]
> 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 DengklekTryingToSleep { public: > 29 int minDucks(vector <int> ducks) > 30 { > 31 int A = *min_element(ducks.begin(), ducks.end()); > 32 int B = *max_element(ducks.begin(), ducks.end()); > 33 return (B-A+1) - ducks.size(); > 34 } > 35 }; > 36 > 37 // BEGIN CUT HERE > 38 #include <ctime> > 39 double start_time; string timer() > 40 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 41 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 42 { os << "{ "; > 43 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 44 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 45 void verify_case(const int& Expected, const int& Received) { > 46 bool ok = (Expected == Received); > 47 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 48 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 49 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 50 #define END verify_case(_, DengklekTryingToSleep().minDucks(ducks));} > 51 int main(){ > 52 > 53 CASE(0) > 54 int ducks_[] = {5, 3, 2}; > 55 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 56 int _ = 1; > 57 END > 58 CASE(1) > 59 int ducks_[] = {58}; > 60 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 61 int _ = 0; > 62 END > 63 CASE(2) > 64 int ducks_[] = {9, 3, 6, 4}; > 65 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 66 int _ = 3; > 67 END > 68 CASE(3) > 69 int ducks_[] = {7, 4, 77, 47, 74, 44}; > 70 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 71 int _ = 68; > 72 END > 73 CASE(4) > 74 int ducks_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > 75 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 76 int _ = 0; > 77 END > 78 /* > 79 CASE(5) > 80 int ducks_[] = ; > 81 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 82 int _ = ; > 83 END > 84 CASE(6) > 85 int ducks_[] = ; > 86 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 87 int _ = ; > 88 END > 89 */ > 90 } > 91 // END CUT HERE
Added SRM/532-U/2C.cpp version [a3d3d1115263fbcb]
> 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 template<typename T> > 29 struct DP3 > 30 { > 31 int N1, N2, N3; > 32 vector<T> data; > 33 DP3(int N1, int N2, int N3, const T& t = T()) > 34 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() > 35 T& operator()(int i1, int i2, int i3) > 36 { return data[ ((i1*N2)+i2)*N3+i3 ]; } > 37 void swap(DP3& rhs) > 38 { data.swap(rhs.data); } > 39 }; > 40 > 41 static const int MODVAL = 1000000007; // must be prime for op/ > 42 struct mint > 43 { > 44 int val; > 45 mint():val(0){} > 46 mint(int x):val(x%MODVAL) {} // x>=0 > 47 mint(size_t x):val(x%MODVAL) {} // x>=0 > 48 mint(LL x):val(x%MODVAL) {} // x>=0 > 49 }; > 50 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 51 mint operator+(mint x, mint y) { return x+=y; } > 52 > 53 class DengklekPaintingSquares { public: > 54 int numSolutions(int N, int M) > 55 { > 56 int END=1; for(int i=0; i<M-1; ++i) END*=3; > 57 DP3<int> memo(N, M, END*3, -1); > 58 return rec(memo, N, M, END, -1, M, 0); > 59 } > 60 > 61 int rec(DP3<int>& memo, const int H, const int W, const int END, int y, > 62 { > 63 if( x == W ) > 64 ++y, x=0; > 65 if( y == H ) > 66 return valid(state) ? 1 : 0; > 67 > 68 if( memo(y,x,state)!=-1 ) > 69 return memo(y,x,state); > 70 > 71 mint total = 0; > 72 int old = state%3; > 73 int pre = state/END%3; > 74 bool put=(old==0 || old==1), nut=(old==0 || old==2); > 75 int parity = (old>=1) ^ (x==0 ? 0 : pre>=1); > 76 if( x == 0 || pre == 0 ) { > 77 if(put) total += rec(memo, H, W, END, y, x+1, state/3 + > 78 if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + > 79 } else { > 80 if(put) total += rec(memo, H, W, END, y, x+1, (state-pre > 81 if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + > 82 } > 83 return memo(y,x,state) = total.val; > 84 } > 85 > 86 bool valid(int state) > 87 { > 88 for(; state; state/=3) > 89 if(state%3 == 1) > 90 return false; > 91 return true; > 92 } > 93 }; > 94 > 95 // BEGIN CUT HERE > 96 #include <ctime> > 97 double start_time; string timer() > 98 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 99 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 100 { os << "{ "; > 101 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 102 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 103 void verify_case(const int& Expected, const int& Received) { > 104 bool ok = (Expected == Received); > 105 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, DengklekPaintingSquares().numSolutions(N, M));} > 109 int main(){ > 110 > 111 CASE(0) > 112 int N = 1; > 113 int M = 1; > 114 int _ = 2; > 115 END > 116 CASE(1) > 117 int N = 2; > 118 int M = 2; > 119 int _ = 8; > 120 END > 121 CASE(2) > 122 int N = 1; > 123 int M = 3; > 124 int _ = 5; > 125 END > 126 CASE(3) > 127 int N = 47; > 128 int M = 7; > 129 int _ = 944149920; > 130 END > 131 CASE(4) > 132 int N = 81; > 133 int M = 8; > 134 int _ = -1; > 135 END > 136 /* > 137 CASE(5) > 138 int N = ; > 139 int M = ; > 140 int _ = ; > 141 END > 142 */ > 143 } > 144 // END CUT HERE
Added SRM/534-U/1A.cpp version [ff253b1becebd348]
> 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 EllysCheckers { public: > 29 string getWinner(string board) > 30 { > 31 int N = board.size()-1; > 32 int mask = 0; > 33 for(int i=0; i<N; ++i) > 34 mask |= (board[i]=='o')<<i; > 35 vector<int> memo(1<<N, -1); > 36 return win(memo, N, mask) ? "YES" : "NO"; > 37 } > 38 > 39 bool win(vector<int>& memo, int N, int mask) > 40 { > 41 mask &= (1<<N)-1; > 42 if( memo[mask] != -1 ) > 43 return memo[mask]; > 44 if( mask == 0 ) // no checker, no move => lose > 45 return 0; > 46 > 47 bool I_win = false; > 48 // enumerate all possible moves > 49 for(int i=0; i<N; ++i) > 50 if( mask & (1<<i) ) { > 51 if( !(mask & (1<<i+1)) ) { // step > 52 int newmask = mask &~ (1<<i) | (1<<i+1); > 53 if( !win(memo, N, newmask) ) > 54 I_win = true; > 55 } > 56 if( (mask & (1<<i+1)) && (mask & (1<<i+2)) && !( > 57 int newmask = mask &~ (1<<i) | (1<<i+3); > 58 if( !win(memo, N, newmask) ) > 59 I_win = true; > 60 } > 61 } > 62 return memo[mask] = I_win; > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const string& Expected, const string& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, EllysCheckers().getWinner(board));} > 80 int main(){ > 81 > 82 CASE(0) > 83 string board = ".o..."; > 84 string _ = "YES"; > 85 END > 86 CASE(1) > 87 string board = "..o..o"; > 88 string _ = "YES"; > 89 END > 90 CASE(2) > 91 string board = ".o...ooo..oo.."; > 92 string _ = "NO"; > 93 END > 94 CASE(3) > 95 string board = "......o.ooo.o......"; > 96 string _ = "YES"; > 97 END > 98 CASE(4) > 99 string board = ".o..o...o....o.....o"; > 100 string _ = "NO"; > 101 END > 102 CASE(5) > 103 string board = "oooooooooooooooooooo"; > 104 string _ = "?"; > 105 END > 106 CASE(6) > 107 string board = "o.o.o.o.o.o.o.o.o.o."; > 108 string _ = "?"; > 109 END > 110 CASE(7) > 111 string board = "."; > 112 string _ = "NO"; > 113 END > 114 CASE(8) > 115 string board = "."; > 116 string _ = "NO"; > 117 END > 118 CASE(9) > 119 string board = "o."; > 120 string _ = "YES"; > 121 END > 122 > 123 } > 124 // END CUT HERE
Added SRM/534-U/1B.cpp version [db25efd7570142d9]
> 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 LL gcd(LL a, LL b) > 29 { > 30 while(a) > 31 swap(a, b%=a); > 32 return b; > 33 } > 34 > 35 class EllysNumbers { public: > 36 long long getSubsets(long long n, vector <string> special) > 37 { > 38 vector<LL> sp; { > 39 stringstream sin( accumulate(special.begin(), special.en > 40 for(LL v; sin>>v; ) > 41 if(n%v==0 && gcd(n/v,v)==1) > 42 sp.push_back(v); > 43 } > 44 > 45 map<LL, LL> w; > 46 w[n] = 1; > 47 for(int i=0; i<sp.size(); ++i) > 48 for(map<LL, LL>::iterator it=w.begin(); it!=w.end(); ++i > 49 if(it->first%sp[i]==0) > 50 w[it->first/sp[i]] += it->second; > 51 return w[1]; > 52 } > 53 }; > 54 > 55 // BEGIN CUT HERE > 56 #include <ctime> > 57 double start_time; string timer() > 58 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 59 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 60 { os << "{ "; > 61 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 62 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 63 void verify_case(const long long& Expected, const long long& Received) { > 64 bool ok = (Expected == Received); > 65 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 66 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 67 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 68 #define END verify_case(_, EllysNumbers().getSubsets(n, special));} > 69 int main(){ > 70 > 71 CASE(0) > 72 long long n = 12LL; > 73 string special_[] = {"4 2 5 6 3"}; > 74 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 75 long long _ = 1LL; > 76 END > 77 CASE(1) > 78 long long n = 42LL; > 79 string special_[] = {"1 2 3 4 5 6 7 13 14 21 42"}; > 80 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 81 long long _ = 10LL; > 82 END > 83 CASE(2) > 84 long long n = 1337LL; > 85 string special_[] = {"1 13 42 666 2674"}; > 86 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 87 long long _ = 0LL; > 88 END > 89 CASE(3) > 90 long long n = 1073741824LL; > 91 string special_[] = {"1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 1 > 92 "6384 32768 65536 131072 262144 524288 1048576 2097", > 93 "152 4194304 8388608 16777216 33554432 67108864 134", > 94 "217728 268435456 536870912"}; > 95 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 96 long long _ = 0LL; > 97 END > 98 CASE(4) > 99 long long n = 7420738134810LL; > 100 string special_[] = {"435 625199055 4199 33263 17 222870 284870433 72093 > 101 "2379 7 11 31 247110827 23 1771 81809 851968487 13 ", > 102 "476379795 1001 5 435274114 38264554 7429 239906525", > 103 " 3 227183706 887045414 606786670 3795 797605175 29", > 104 " 30 747186719 19 2 562347843 74 2294 588002688 743", > 105 "6429 703 591740547 36657492 37 444178205 1002001 2", > 106 "17626404"}; > 107 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 108 long long _ = 110LL; > 109 END > 110 CASE(5) > 111 long long n = 1LL<<45; > 112 string special_[] = {"1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 1 > 113 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 114 long long _ = 0LL; > 115 END > 116 CASE(7) > 117 long long n = 614889782588491410LL; > 118 string special_[] = {"2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 6 10 14 2 > 119 vector <string> special(special_, special_+sizeof(special_)/sizeof(*sp > 120 long long _ = 188811356LL; > 121 END > 122 } > 123 // END CUT HERE
Added SRM/534-U/1C-U.cpp version [d4a4f9e31f2db32b]
> 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 EllysString { public: > 29 int theMin(vector <string> s, vector <string> t) > 30 { > 31 string S = accumulate(s.begin(), s.end(), string("")); > 32 string T = accumulate(t.begin(), t.end(), string("")); > 33 int N = S.size(); > 34 int total = 0; > 35 for(int i=0; i<N; ) > 36 { > 37 if( S[i] == T[i] ) { > 38 ++i; > 39 continue; > 40 } > 41 int rot_k = -1; > 42 > 43 // abcdef > 44 // bcdefa > 45 for(int k=i+1; k<N; ++k) > 46 { > 47 if( S[k] != T[k-1] ) > 48 break; > 49 if( T[k] == S[i] ) > 50 rot_k = max(rot_k, k+1); > 51 } > 52 // bcdefa > 53 // abcdef > 54 for(int k=i+1; k<N; ++k) > 55 { > 56 if( T[k] != S[k-1] ) > 57 break; > 58 if( S[k] == T[i] ) > 59 rot_k = max(rot_k, k+1); > 60 } > 61 > 62 if( rot_k == -1 ) { > 63 total += 1; > 64 ++i; > 65 continue; > 66 } else { > 67 total += rot_k - i - 1; > 68 i = rot_k; > 69 continue; > 70 } > 71 } > 72 return total; > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const int& Expected, const int& Received) { > 85 bool ok = (Expected == Received); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, EllysString().theMin(s, t));} > 90 int main(){ > 91 > 92 CASE(0) > 93 string s_[] = {"usagi"}; > 94 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 95 string t_[] = {"unagi"}; > 96 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 97 int _ = 1; > 98 END > 99 CASE(1) > 100 string s_[] = {"unagi"}; > 101 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 102 string t_[] = {"nugai"}; > 103 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 104 int _ = 2; > 105 END > 106 CASE(2) > 107 string s_[] = {"ellys", "string"}; > 108 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 109 string t_[] = {"e", "ll", "ysst", "ring"}; > 110 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 111 int _ = 0; > 112 END > 113 CASE(3) > 114 string s_[] = {"fox"}; > 115 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 116 string t_[] = {"xfo"}; > 117 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 118 int _ = 2; > 119 END > 120 CASE(4) > 121 string s_[] = {"salmon"}; > 122 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 123 string t_[] = {"camlon"}; > 124 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 125 int _ = 2; > 126 END > 127 CASE(5) > 128 string s_[] = {"boajxuidva"}; > 129 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 130 string t_[] = {"jcayduvida"}; > 131 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 132 int _ = 6; > 133 END > 134 CASE(6) > 135 string s_[] = {"vykdnujyezbcbmnatipqfuxqmgkvtn"}; > 136 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 137 string t_[] = {"qokbqyujeqcbwsinatupqfoegmvkdz"}; > 138 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 139 int _ = 22; > 140 END > 141 /* > 142 CASE(7) > 143 string s_[] = ; > 144 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 145 string t_[] = ; > 146 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 147 int _ = ; > 148 END > 149 CASE(8) > 150 string s_[] = ; > 151 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 152 string t_[] = ; > 153 vector <string> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 154 int _ = ; > 155 END > 156 */ > 157 } > 158 // END CUT HERE
Modified lib/typical/amap.cpp from [8e84d319ff86cb61] to [7a3d2ba79608ced5].
5 // overflows, it eliminates duplication 5 // overflows, it eliminates duplication 6 // 6 // 7 7 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> 9 struct amap 9 struct amap 10 { 10 { 11 typedef typename vector< pair<K,V> >::iterator iterator; 11 typedef typename vector< pair<K,V> >::iterator iterator; > 12 struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) c 12 13 13 vector< pair<K,V> > kv; 14 vector< pair<K,V> > kv; 14 amap() { kv.reserve(LIMIT); } 15 amap() { kv.reserve(LIMIT); } 15 16 16 void add(const K& k, const V& v) 17 void add(const K& k, const V& v) 17 { 18 { 18 kv.push_back( make_pair(k,v) ); 19 kv.push_back( make_pair(k,v) ); ................................................................................................................................................................................ 20 normalize(); 21 normalize(); 21 } 22 } 22 23 23 iterator begin() { return kv.begin(); } 24 iterator begin() { return kv.begin(); } 24 iterator end() { return kv.end(); } 25 iterator end() { return kv.end(); } 25 void swap( amap& rhs ) { kv.swap(rhs.kv); } 26 void swap( amap& rhs ) { kv.swap(rhs.kv); } 26 27 27 // Tested: SRM 469 Lv3 | 28 // Tested: SRM 469 Lv3 (Accumulate) 28 void normalize() 29 void normalize() 29 { 30 { 30 sort(kv.begin(), kv.end()); | 31 sort(kv.begin(), kv.end(), ByKey()); 31 int i=0; 32 int i=0; 32 for(int j=0; j<kv.size(); ++i) 33 for(int j=0; j<kv.size(); ++i) 33 { 34 { 34 int k = j; 35 int k = j; 35 kv[i] = kv[k]; 36 kv[i] = kv[k]; 36 while( ++j<kv.size() && kv[k].first==kv[j].first ) 37 while( ++j<kv.size() && kv[k].first==kv[j].first ) 37 kv[i].second += kv[j].second; 38 kv[i].second += kv[j].second; ................................................................................................................................................................................ 38 } 39 } 39 kv.resize(i); 40 kv.resize(i); 40 } 41 } 41 /* 42 /* 42 // Not Tested (Prefer First) 43 // Not Tested (Prefer First) 43 void normalize() 44 void normalize() 44 { 45 { 45 sort(kv.begin(), kv.end()); | 46 sort(kv.begin(), kv.end(), ByKey()); 46 int i=0; 47 int i=0; 47 for(int j=0; j<kv.size(); ++i) 48 for(int j=0; j<kv.size(); ++i) 48 { 49 { 49 int k = j; 50 int k = j; 50 kv[i] = kv[k]; 51 kv[i] = kv[k]; 51 while( ++j<kv.size() && kv[k].first==kv[j].first ) 52 while( ++j<kv.size() && kv[k].first==kv[j].first ) 52 {} 53 {} ................................................................................................................................................................................ 53 } 54 } 54 kv.resize(i); 55 kv.resize(i); 55 } 56 } 56 57 57 // Not Tested (Prefer Last) 58 // Not Tested (Prefer Last) 58 void normalize() 59 void normalize() 59 { 60 { 60 sort(kv.begin(), kv.end()); | 61 sort(kv.begin(), kv.end(), ByKey()); 61 int i=0; 62 int i=0; 62 for(int j=0; j<kv.size(); ++i) 63 for(int j=0; j<kv.size(); ++i) 63 { 64 { 64 int k = j; 65 int k = j; 65 while( ++j<kv.size() && kv[k].first==kv[j].first ) 66 while( ++j<kv.size() && kv[k].first==kv[j].first ) 66 {} 67 {} 67 kv[i] = kv[j-1]; 68 kv[i] = kv[j-1]; 68 } 69 } 69 kv.resize(i); 70 kv.resize(i); 70 } 71 } 71 */ 72 */ 72 }; 73 };