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) < 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 < 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() < 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 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, < 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 #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 using namespace std; 17 using namespace std; 19 typedef long long LL; 18 typedef long long LL; > 19 typedef long double LD; 20 typedef complex<double> CMP; | 20 typedef complex<LD> CMP; 21 21 22 class WhiteSpaceEditing { public: 22 class WhiteSpaceEditing { public: 23 int getMinimum(vector <int> lines) 23 int getMinimum(vector <int> lines) 24 { 24 { 25 const int N = lines.size(); < 26 const int V = *max_element(lines.begin(), lines.end()); | 25 set<int> slen(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) < > 26 slen.insert(0); 31 { | 27 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; < > 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); 36 } | 31 } 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 } | 32 42 dp.swap(dp_neo); < > 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]); 43 } | 38 > 39 int key = (s*(lines.size()+1)+e)*len.size()+cur_len; > 40 if(memo[key] != -1) 44 return dp[0] + N-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(le > 49 return memo[key] = result; 45 } 50 } 46 }; 51 }; 47 52 48 // BEGIN CUT HERE 53 // BEGIN CUT HERE 49 #include <ctime> 54 #include <ctime> 50 double start_time; string timer() 55 double start_time; string timer() 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) ................................................................................................................................................................................ 79 END 84 END 80 CASE(3) 85 CASE(3) 81 int lines_[] = { 250, 105, 155, 205, 350 } 86 int lines_[] = { 250, 105, 155, 205, 350 } 82 ; 87 ; 83 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 84 int _ = 499; 89 int _ = 499; 85 END 90 END > 91 /* 86 CASE(4) 92 CASE(4) 87 int lines_[] = {0}; | 93 int lines_[] = ; 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 94 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 89 int _ = 0; | 95 int _ = ; 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 END 96 CASE(5) 97 CASE(5) 97 int lines_[] = {10}; | 98 int lines_[] = ; 98 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 99 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 99 int _ = 10; | 100 int _ = ; 100 END 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, < 108 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 109 int _ = 1000049; < 110 END < 111 < > 102 */ 112 } 103 } 113 // END CUT HERE 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) > 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 > 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() > 78 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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) > 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 > 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() > 97 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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)< > 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> > > 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) > 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 > 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() > 145 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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<>", " > 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 // Strongly Connected Component of a Directed Graph 3 // Strongly Connected Component of a Directed Graph 4 // O(E) 4 // O(E) 5 // 5 // 6 // Verified by 6 // Verified by 7 // - SRM 499 Div1 LV3 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 template<typename T> 12 template<typename T> 13 class IdGen 13 class IdGen 14 { 14 { 15 map<T, int> v2id_; 15 map<T, int> v2id_; 16 vector<T> id2v_; 16 vector<T> id2v_;