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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 48 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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()*sizeof(T)<(1<<26)); } 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, int x, int state) 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 + (2-parity)*END); 78 + if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + 0*END); 79 + } else { 80 + if(put) total += rec(memo, H, W, END, y, x+1, (state-pre*END)/3 + (3-pre)*(END/3) + (2-parity)*END); 81 + if(nut) total += rec(memo, H, W, END, y, x+1, state/3 + 0*END); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 106 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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)) && !(mask & (1<<i+3)) ) { // jump 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 77 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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.end(), string("")) ); 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(); ++it) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 66 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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(*special_)); 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(*special_)); 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(*special_)); 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(*special_)); 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(*special_)); 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 16384"}; 113 + vector <string> special(special_, special_+sizeof(special_)/sizeof(*special_)); 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", "2 26 34 38 46 58 62 74 82 86 94 15 21 33 39 51 57 ", "69 87 93 111 123 129 141 35 55 65 85 95 115 145 15", "5 185 205 215 235 77 91 119 133 161 203 217 259 28", "7 301 329 143 187 209 253 319 341 407 451 473 517 ", "221 247 299 377 403 481 533 559 611 323 391 493 52", "7 629 697 731 799 437 551 589 703 779 817 893 667 ", "713 851 943 989 1081 899 1073 1189 1247 1363 1147 ", "1271 1333 1457 1517 1591 1739 1763 1927 2021 11803", " 18377 2337 1479 1886 4945 4199 71299 6235 246 982", "3 4921 8569 14053 16813 31487 17719 1426 2109 258 ", "16967 22607 13243 2001 4495 3059 2553 4403 1598 35", "65 9635 9541 310 2849 5453 6923 3857 1885 645 2303", " 14663 36859 6721 658 2091 1833 1419 32759 68413 3", "995 34891 55883 2233 5945 10199 222 2542 1595 1616", "9 23693 741 7657 2255 3485 43993 4123 40549 26381 ", "2465 41971 5781 29971 387 1551 230 8177 20213 1912", "9 1443 22231 7567 11339 8897 627 638 12617 2737 14", "35 651 14467 20539 987 5217 12673 2193 3367 62651 ", "24679 418 186 12121 5117 1767 4301 238 9889 1798 8", "987 1677 7733 261 2666 13079 16027 1034 1547 3034 ", "17081 8029 2365 465 11687 20683 75 13717 345 561 3", "9997 5423 7429 28681 14147 29233 3619 16211 22591 ", "59737 52111 897 24863 5797 34481 266 1558 374 1061", "9 3895 2139 1702 2639 1394 1421 2635 102 4147 3689", " 8959 429 285 27683 442 2397 18241 4277 6919 325 1", "4993 2783 1066 3451 20387 6601 1118 114 36613 1189", "1 1505 518 42 16687 5957 1462 7337 3741 12259 9331", " 231 3441 273 5819 18491 470 1599 9139 2717 10127 ", "1653 2755 2494 5735 9061 705 874 65231 15181 1771 ", "195 435 130 867 2093 33497 29563 182 33041 4879 66", "5 16523 4371 1023 1222 8729 3731 5593 1311 4715 77", "7 370 935 17917 8041 969 6665 4089 24037 13547 229", "4 6149 322 38657 2697 946 4669 1265 38399 6355 100", "13 24149 814 7163 1105 7285 1634 3478 2405 2795 20", "677 2162 1786 609 31349 4807 10621 188 646 6409 17", "29 9361 25897 385 3553 3157 46139 1978 105 46483 1", "9393 962 11951 30229 53621 30659 3243 42253 615 60", "2 25327 1258 3219 3515 861 13889 595 9367 1054 606", "1 682 78 39527 6293 8695 423 6727 2378 15979 138 5", "289 8323 1015 833 21793 5681 2665 35131 16031 410 ", "1058 5863 1295 2015 1334 2967 27869 15283 6063 123", "41 174 44321 24769 124 1615 33263 53909 56129 1113", "7 1309 154 5291 1887 21607 13583 7667 11063 9503 4", "06 931 754 20 30 4773 28823 3854 110 17329 715 506", " 430 574 153 1085 282 2914 82861 1209 3813 1463 11", "31 2387 2146 10105 4551 5719 7585 1353 3655 3055 1", "221 2035 22103 902"}; 119 + vector <string> special(special_, special_+sizeof(special_)/sizeof(*special_)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 87 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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 5 // overflows, it eliminates duplication 6 6 // 7 7 8 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> 9 9 struct amap 10 10 { 11 11 typedef typename vector< pair<K,V> >::iterator iterator; 12 + struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) const { return a.first<b.first; } }; 12 13 13 14 vector< pair<K,V> > kv; 14 15 amap() { kv.reserve(LIMIT); } 15 16 16 17 void add(const K& k, const V& v) 17 18 { 18 19 kv.push_back( make_pair(k,v) ); ................................................................................ 20 21 normalize(); 21 22 } 22 23 23 24 iterator begin() { return kv.begin(); } 24 25 iterator end() { return kv.end(); } 25 26 void swap( amap& rhs ) { kv.swap(rhs.kv); } 26 27 27 - // Tested: SRM 469 Lv3 28 + // Tested: SRM 469 Lv3 (Accumulate) 28 29 void normalize() 29 30 { 30 - sort(kv.begin(), kv.end()); 31 + sort(kv.begin(), kv.end(), ByKey()); 31 32 int i=0; 32 33 for(int j=0; j<kv.size(); ++i) 33 34 { 34 35 int k = j; 35 36 kv[i] = kv[k]; 36 37 while( ++j<kv.size() && kv[k].first==kv[j].first ) 37 38 kv[i].second += kv[j].second; ................................................................................ 38 39 } 39 40 kv.resize(i); 40 41 } 41 42 /* 42 43 // Not Tested (Prefer First) 43 44 void normalize() 44 45 { 45 - sort(kv.begin(), kv.end()); 46 + sort(kv.begin(), kv.end(), ByKey()); 46 47 int i=0; 47 48 for(int j=0; j<kv.size(); ++i) 48 49 { 49 50 int k = j; 50 51 kv[i] = kv[k]; 51 52 while( ++j<kv.size() && kv[k].first==kv[j].first ) 52 53 {} ................................................................................ 53 54 } 54 55 kv.resize(i); 55 56 } 56 57 57 58 // Not Tested (Prefer Last) 58 59 void normalize() 59 60 { 60 - sort(kv.begin(), kv.end()); 61 + sort(kv.begin(), kv.end(), ByKey()); 61 62 int i=0; 62 63 for(int j=0; j<kv.size(); ++i) 63 64 { 64 65 int k = j; 65 66 while( ++j<kv.size() && kv[k].first==kv[j].first ) 66 67 {} 67 68 kv[i] = kv[j-1]; 68 69 } 69 70 kv.resize(i); 70 71 } 71 72 */ 72 73 };