Overview
| SHA1 Hash: | 109f2a905054214ee783c25b3be35ae7c30f78fd |
|---|---|
| Date: | 2012-09-08 04:01:47 |
| User: | kinaba |
| Comment: | 555 |
| 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
Deleted SRM/499/1B-U.cpp version [13e543b5a0b1db44]
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 -using namespace std; 19 -typedef long long LL; 20 -typedef complex<double> CMP; 21 - 22 -class WhiteSpaceEditing { public: 23 - int getMinimum(vector <int> lines) 24 - { 25 - const int N = lines.size(); 26 - const int V = *max_element(lines.begin(), lines.end()); 27 - vector<int> dp(V+1), dp_neo(V+1); 28 - for(int v=0; v<=V; ++v) 29 - dp[v] = abs(v - lines[N-1]); 30 - for(int i=N-2; i>=0; --i) 31 - { 32 - int best = INT_MAX; 33 - for(int v=lines[i]; v>=0; --v) { 34 - best = min(best, dp[v]); 35 - dp_neo[v] = abs(v - lines[i]) + best; 36 - } 37 - best = INT_MAX; 38 - for(int v=lines[i]; v<=V; ++v) { 39 - best = min(best, dp[v]); 40 - dp_neo[v] = abs(v - lines[i]) + best; 41 - } 42 - dp.swap(dp_neo); 43 - } 44 - return dp[0] + N-1; 45 - } 46 -}; 47 - 48 -// BEGIN CUT HERE 49 -#include <ctime> 50 -double start_time; string timer() 51 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 52 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 53 - { os << "{ "; 54 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 55 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 56 -void verify_case(const int& Expected, const int& Received) { 57 - bool ok = (Expected == Received); 58 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 59 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 60 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 61 -#define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} 62 -int main(){ 63 - 64 -CASE(0) 65 - int lines_[] = { 3, 2, 3 }; 66 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 67 - int _ = 6; 68 -END 69 -CASE(1) 70 - int lines_[] = { 0 }; 71 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 72 - int _ = 0; 73 -END 74 -CASE(2) 75 - int lines_[] = { 1, 2, 4 } 76 -; 77 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 78 - int _ = 6; 79 -END 80 -CASE(3) 81 - int lines_[] = { 250, 105, 155, 205, 350 } 82 -; 83 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 84 - int _ = 499; 85 -END 86 -CASE(4) 87 -int lines_[] = {0}; 88 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 89 - int _ = 0; 90 -END 91 -CASE(5) 92 -int lines_[] = {1}; 93 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 94 - int _ = 1; 95 -END 96 -CASE(5) 97 - int lines_[] = {10}; 98 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 99 - int _ = 10; 100 -END 101 -CASE(5) 102 - int lines_[] = {10,10}; 103 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 104 - int _ = 11; 105 -END 106 -CASE(5) 107 - int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}; 108 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109 - int _ = 1000049; 110 -END 111 - 112 -} 113 -// END CUT HERE
Modified SRM/499/1B.cpp from [13e543b5a0b1db44] to [124c7549ad607d0d].
10 10 #include <iterator> 11 11 #include <functional> 12 12 #include <complex> 13 13 #include <queue> 14 14 #include <stack> 15 15 #include <cmath> 16 16 #include <cassert> 17 -#include <cstring> 18 17 using namespace std; 19 18 typedef long long LL; 20 -typedef complex<double> CMP; 19 +typedef long double LD; 20 +typedef complex<LD> CMP; 21 21 22 22 class WhiteSpaceEditing { public: 23 23 int getMinimum(vector <int> lines) 24 24 { 25 - const int N = lines.size(); 26 - const int V = *max_element(lines.begin(), lines.end()); 27 - vector<int> dp(V+1), dp_neo(V+1); 28 - for(int v=0; v<=V; ++v) 29 - dp[v] = abs(v - lines[N-1]); 30 - for(int i=N-2; i>=0; --i) 31 - { 32 - int best = INT_MAX; 33 - for(int v=lines[i]; v>=0; --v) { 34 - best = min(best, dp[v]); 35 - dp_neo[v] = abs(v - lines[i]) + best; 36 - } 37 - best = INT_MAX; 38 - for(int v=lines[i]; v<=V; ++v) { 39 - best = min(best, dp[v]); 40 - dp_neo[v] = abs(v - lines[i]) + best; 41 - } 42 - dp.swap(dp_neo); 43 - } 44 - return dp[0] + N-1; 25 + set<int> slen(lines.begin(), lines.end()); 26 + slen.insert(0); 27 + 28 + vector<int> len(slen.begin(), slen.end()); 29 + memo.assign(lines.size()*(lines.size()+1)*len.size(), -1); 30 + return rec(lines, 0, lines.size(), len, 0) + (lines.size()-1); 31 + } 32 + 33 + vector<int> memo; 34 + int rec(const vector<int>& lines, int s, int e, 35 + const vector<int>& len, int cur_len) { 36 + if(s+1 == e) 37 + return abs(lines[s] - len[cur_len]); 38 + 39 + int key = (s*(lines.size()+1)+e)*len.size()+cur_len; 40 + if(memo[key] != -1) 41 + return memo[key]; 42 + 43 + int result = 0x1fffffff; 44 + for(int base_len=0; base_len<len.size(); ++base_len) 45 + for(int m=s+1; m<e; ++m) 46 + result = min(result, 47 + rec(lines, s, m, len, base_len) + 48 + rec(lines, m, e, len, base_len) + abs(len[cur_len] - len[base_len])); 49 + return memo[key] = result; 45 50 } 46 51 }; 47 52 48 53 // BEGIN CUT HERE 49 54 #include <ctime> 50 55 double start_time; string timer() 51 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ................................................................................ 79 84 END 80 85 CASE(3) 81 86 int lines_[] = { 250, 105, 155, 205, 350 } 82 87 ; 83 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 84 89 int _ = 499; 85 90 END 91 +/* 86 92 CASE(4) 87 -int lines_[] = {0}; 93 + int lines_[] = ; 88 94 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 89 - int _ = 0; 90 -END 91 -CASE(5) 92 -int lines_[] = {1}; 93 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 94 - int _ = 1; 95 + int _ = ; 95 96 END 96 97 CASE(5) 97 - int lines_[] = {10}; 98 + int lines_[] = ; 98 99 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 99 - int _ = 10; 100 + int _ = ; 100 101 END 101 -CASE(5) 102 - int lines_[] = {10,10}; 103 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 104 - int _ = 11; 105 -END 106 -CASE(5) 107 - int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}; 108 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109 - int _ = 1000049; 110 -END 111 - 102 +*/ 112 103 } 113 104 // END CUT HERE
Added SRM/555-U/1A.cpp version [f68efed934ab056b]
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 +class CuttingBitString { public: 23 + static const int INF = 999; 24 + 25 + int getmin(string S) 26 + { 27 + LL v = 1; 28 + set<string> good; 29 + for(LL v=1; v<(1LL<<60); v*=5) { 30 + cerr << bin(v) << endl; 31 + good.insert(bin(v)); 32 + } 33 + 34 + int s = best(S, good, 0, S.size()); 35 + return s>=INF ? -1 : s; 36 + } 37 + 38 + map<pair<int,int>, int> memo; 39 + int best(const string& S, const set<string>& good, int s, int e) 40 + { 41 + pair<int,int> key(s,e); 42 + if(memo.count(key)) 43 + return memo[key]; 44 + 45 + if( good.count(S.substr(s, e-s)) ) 46 + return memo[key] = 1; 47 + int score = INF; 48 + for(int m=s+1; m+1<=e; ++m) 49 + { 50 + int x = best(S, good, s, m); 51 + int y = best(S, good, m, e); 52 + score = min(score, x+y); 53 + } 54 + return memo[key] = score; 55 + } 56 + 57 + string bin(LL v) 58 + { 59 + string s; 60 + for(; v; v>>=1) 61 + s += (v&1 ? '1' : '0'); 62 + reverse(s.begin(), s.end()); 63 + return s; 64 + } 65 +}; 66 + 67 +// BEGIN CUT HERE 68 +#include <ctime> 69 +double start_time; string timer() 70 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 71 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 72 + { os << "{ "; 73 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 74 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 75 +void verify_case(const int& Expected, const int& Received) { 76 + bool ok = (Expected == Received); 77 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 78 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 79 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 80 +#define END verify_case(_, CuttingBitString().getmin(S));} 81 +int main(){ 82 + 83 +CASE(3) 84 + string S = "110011011"; 85 + int _ = 3; 86 +END 87 +CASE(0) 88 + string S = "101101101"; 89 + int _ = 3; 90 +END 91 +CASE(1) 92 + string S = "1111101"; 93 + int _ = 1; 94 +END 95 +CASE(2) 96 + string S = "00000"; 97 + int _ = -1; 98 +END 99 +CASE(4) 100 + string S = "1000101011"; 101 + int _ = -1; 102 +END 103 +CASE(5) 104 + string S = "111011100110101100101110111"; 105 + int _ = 5; 106 +END 107 +CASE(6) 108 + string S = "11111111111111111111111111111111111111111111111111"; 109 + int _ = -999; 110 +END 111 +CASE(7) 112 + string S = "1101100011010111001001101011011100010111011110101"; 113 + int _ = 1; 114 +END 115 +} 116 +// END CUT HERE
Added SRM/555-U/1B.cpp version [d81e904d5ff64153]
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 +static const unsigned MODVAL = 555555555; 23 +struct mint 24 +{ 25 + unsigned val; 26 + mint():val(0){} 27 + mint(int x):val(x%MODVAL) {} 28 + mint(unsigned x):val(x%MODVAL) {} 29 + mint(LL x):val(x%MODVAL) {} 30 +}; 31 +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 32 +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 33 +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 34 +mint operator+(mint x, mint y) { return x+=y; } 35 +mint operator-(mint x, mint y) { return x-=y; } 36 +mint operator*(mint x, mint y) { return x*=y; } 37 +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 38 + 39 +vector< vector<mint> > CP_; 40 +mint C(LL n, LL k) { 41 + while( CP_.size() <= n ) { 42 + int nn = CP_.size(); 43 + CP_.push_back(vector<mint>(nn+1,1)); 44 + for(int kk=1; kk<nn; ++kk) 45 + CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 46 + } 47 + return k<0 || n<k ? 0 : CP_[n][k]; 48 +} 49 + 50 +class XorBoard { public: 51 + int count(int H, int W, int Rcount, int Ccount, int S) 52 + { 53 + vector<mint> xx(W+1), yy(H+1); 54 + for(int x=0; x<=W; ++x) 55 + xx[x] = subProblem(W, Ccount, x); 56 + for(int y=0; y<=H; ++y) 57 + yy[y] = subProblem(H, Rcount, y); 58 + 59 + mint cnt = 0; 60 + for(int x=0; x<=W; ++x) 61 + for(int y=0; y<=H; ++y) 62 + if( x*(H-y)+(W-x)*y == S ) 63 + cnt += xx[x]*yy[y]; 64 + return cnt.val; 65 + } 66 + 67 + mint subProblem(int Z, int T, int k) 68 + { 69 + // Z objects 70 + // T flips 71 + // k of them flipped odd # of times 72 + // Z-k even 73 + if( T < k ) 74 + return 0; 75 + T -= k; 76 + if( T%2 != 0 ) 77 + return 0; 78 + T /= 2; 79 + mint cc = C(Z, k); 80 + // Z obj 81 + // T flips 82 + return cc * C(T+Z-1, Z-1); 83 + } 84 +}; 85 + 86 +// BEGIN CUT HERE 87 +#include <ctime> 88 +double start_time; string timer() 89 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 90 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 91 + { os << "{ "; 92 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 93 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 94 +void verify_case(const int& Expected, const int& Received) { 95 + bool ok = (Expected == Received); 96 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 97 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 98 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 99 +#define END verify_case(_, XorBoard().count(H, W, Rcount, Ccount, S));} 100 +int main(){ 101 + 102 +CASE(0) 103 + int H = 2; 104 + int W = 2; 105 + int Rcount = 2; 106 + int Ccount = 2; 107 + int S = 4; 108 + int _ = 4; 109 +END 110 +CASE(1) 111 + int H = 2; 112 + int W = 2; 113 + int Rcount = 0; 114 + int Ccount = 0; 115 + int S = 1; 116 + int _ = 0; 117 +END 118 +CASE(2) 119 + int H = 10; 120 + int W = 20; 121 + int Rcount = 50; 122 + int Ccount = 40; 123 + int S = 200; 124 + int _ = 333759825; 125 +END 126 +CASE(3) 127 + int H = 1200; 128 + int W = 1000; 129 + int Rcount = 800; 130 + int Ccount = 600; 131 + int S = 4000; 132 + int _ = 96859710; 133 +END 134 +CASE(4) 135 + int H = 555; 136 + int W = 555; 137 + int Rcount = 555; 138 + int Ccount = 555; 139 + int S = 5550; 140 + int _ = 549361755; 141 +END 142 +CASE(5) 143 + int H = 1555; 144 + int W = 1555; 145 + int Rcount = 755; 146 + int Ccount = 755; 147 + int S = 555555; 148 + int _ = -1; 149 +END 150 +/* 151 +CASE(6) 152 + int H = ; 153 + int W = ; 154 + int Rcount = ; 155 + int Ccount = ; 156 + int S = ; 157 + int _ = ; 158 +END 159 +*/ 160 +} 161 +// END CUT HERE
Added SRM/555-U/1C-U.cpp version [2498e6610d468028]
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 DP2 24 +{ 25 + const int N1, N2; 26 + vector<T> data; 27 + DP2(int N1, int N2, const T& t = T()) 28 + : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); } 29 + T& operator()(int i1, int i2) 30 + { return data[ (i1*N2)+i2 ]; } 31 + void swap(DP2& rhs) 32 + { data.swap(rhs.data); } 33 +}; 34 + 35 +class MapGuessing { public: 36 + long long countPatterns(string goal, vector <string> code_) 37 + { 38 + string code = accumulate(code_.begin(), code_.end(), string("")); 39 + deque<char> pattern(1, '?'); 40 + int head = 0; 41 + for(int i=0; i<code.size(); ++i) 42 + switch(code[i]) 43 + { 44 + case '0': 45 + case '1': 46 + pattern[head] = code[i]; 47 + break; 48 + case '<': 49 + head--; 50 + if(head==-1) { 51 + head = 0; 52 + pattern.push_front('?'); 53 + } 54 + break; 55 + case '>': 56 + head++; 57 + if(head==pattern.size()) 58 + pattern.push_back('?'); 59 + break; 60 + } 61 + return solve(goal, string(pattern.begin(), pattern.end())); 62 + } 63 + 64 + LL solve(const string& G, const string& P) 65 + { 66 + if(P.size() > G.size()) 67 + return 0; 68 + 69 + int N = P.size(); 70 + vector< vector<int> > DFA(N, vector<int>(2)); 71 + for(int i=0; i<N; ++i) 72 + { 73 + int fail = 0; 74 + for(int k=i-1; k>=0; --k) 75 + if( match(P.substr(0, k), P.substr(i-k, k)) 76 + && match(P[k], nega(P[i])) ) { 77 + fail = k; 78 + break; 79 + } 80 + 81 + if(P[i]=='0') 82 + { 83 + DFA[i][0] = i+1; 84 + DFA[i][1] = fail; 85 + } 86 + else if(P[i]=='1') 87 + { 88 + DFA[i][0] = fail; 89 + DFA[i][1] = i+1; 90 + } 91 + else 92 + { 93 + DFA[i][0] = i+1; 94 + DFA[i][1] = i+1; 95 + } 96 + } 97 + 98 + LL total = 0; 99 + for(int s=0; s+P.size()<=G.size(); ++s) 100 + { 101 + LL v = subProblem(s, G, s+P.size(), DFA, N); 102 + total += v; 103 + } 104 + return total; 105 + } 106 + 107 + char nega(char c) { return c=='?' ? c : c=='0' ? '1' : '0'; } 108 + bool match(char a, char b) { 109 + return a=='?' || b=='?' || a==b; 110 + } 111 + bool match(const string& a, const string& b) { 112 + for(int i=0; i<a.size(); ++i) 113 + if(!match(a[i], b[i])) 114 + return false; 115 + return true; 116 + } 117 + 118 + LL subProblem(int s, const string& G, int M, const vector< vector<int> >& DFA, int Q) 119 + { 120 + DP2<LL> dp(M+1, Q+1); 121 + dp(0, 0) = 1; 122 + for(int i=0; i<M; ++i) 123 + for(int q=0; q<Q; ++q) 124 + { 125 + if(s>=i || G[i]=='0') 126 + dp(i+1, DFA[q][0]) += dp(i,q); 127 + if(s>=i || G[i]=='1') 128 + dp(i+1, DFA[q][1]) += dp(i,q); 129 + } 130 + return dp(M, Q); 131 + } 132 +}; 133 + 134 +// BEGIN CUT HERE 135 +#include <ctime> 136 +double start_time; string timer() 137 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 138 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 139 + { os << "{ "; 140 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 141 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 142 +void verify_case(const long long& Expected, const long long& Received) { 143 + bool ok = (Expected == Received); 144 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 145 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 146 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 147 +#define END verify_case(_, MapGuessing().countPatterns(goal, code));} 148 +int main(){ 149 + 150 +CASE(0) 151 + string goal = "000"; 152 + string code_[] = {"0"}; 153 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 154 + long long _ = 4LL; 155 +END 156 +CASE(1) 157 + string goal = "001"; 158 + string code_[] = {"0>1"}; 159 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 160 + long long _ = 5LL; 161 +END 162 +CASE(2) 163 + string goal = "000"; 164 + string code_[] = {"1>1>1"}; 165 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 166 + long long _ = 1LL; 167 +END 168 +CASE(3) 169 + string goal = "11001"; 170 + string code_[] = {">><<<<><<"}; 171 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 172 + long long _ = 0LL; 173 +END 174 +CASE(4) 175 + string goal = "1000101011"; 176 + string code_[] = {"1<<0>>0>1"}; 177 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 178 + long long _ = 22LL; 179 +END 180 +CASE(5) 181 + string goal = "00000010000000000000000000000000"; 182 + string code_[] = {"><>>0<0<>>1>0><>", "<<0>>0<>><0>0>>><><", ">>>0<>", ">0><>>>>0<<><>>0>>>0<0>>0>"}; 183 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 184 + long long _ = 13601LL; 185 +END 186 +CASE(6) 187 + string goal = "11100011010111111010100100110001101"; 188 + string code_[] = {"11111111111111111111" 189 +,"1<><><><><><><><><>1" 190 +,"1<>000>000><0<><0<>1" 191 +,"1<0<><>0><0<00>00<>1" 192 +,"1<>00<>000><0<0<0<>1" 193 +,"1<><>0>0><0<0<><0<>1" 194 +,"1<000<>0><0<0<><0<>1" 195 +,"1<><><><><><><><><>1" 196 +,"1<>000><000<>000><>1" 197 +,"1<>0><><0<><>0><><>1" 198 +,"1<>000><000<>000><>1" 199 +,"1<><>0><><0<><>0><>1" 200 +,"1<>000><000<>000><>1" 201 +,"1<><><><><><><><><>1" 202 +,"11111111111111111111"}; 203 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 204 + long long _ = 90LL; 205 +END 206 +/* 207 +CASE(7) 208 + string goal = ; 209 + string code_[] = ; 210 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 211 + long long _ = LL; 212 +END 213 +CASE(8) 214 + string goal = ; 215 + string code_[] = ; 216 + vector <string> code(code_, code_+sizeof(code_)/sizeof(*code_)); 217 + long long _ = LL; 218 +END 219 + */ 220 +} 221 +// END CUT HERE
Modified lib/graph/scc.cpp from [1f3d1cfa1b9a8b8a] to [b0ca04383cc7283f].
2 2 //------------------------------------------------------------- 3 3 // Strongly Connected Component of a Directed Graph 4 4 // O(E) 5 5 // 6 6 // Verified by 7 7 // - SRM 499 Div1 LV3 8 8 // 9 -// Using "Spagetthi Source"'s one path algorithm 9 +// Using "Spagetthi Source"'s one pass algorithm 10 10 //------------------------------------------------------------- 11 11 12 12 template<typename T> 13 13 class IdGen 14 14 { 15 15 map<T, int> v2id_; 16 16 vector<T> id2v_;