DELETED SRM/499/1B-U.cpp Index: SRM/499/1B-U.cpp ================================================================== --- SRM/499/1B-U.cpp +++ SRM/499/1B-U.cpp @@ -1,113 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -using namespace std; -typedef long long LL; -typedef complex CMP; - -class WhiteSpaceEditing { public: - int getMinimum(vector lines) - { - const int N = lines.size(); - const int V = *max_element(lines.begin(), lines.end()); - vector dp(V+1), dp_neo(V+1); - for(int v=0; v<=V; ++v) - dp[v] = abs(v - lines[N-1]); - for(int i=N-2; i>=0; --i) - { - int best = INT_MAX; - for(int v=lines[i]; v>=0; --v) { - best = min(best, dp[v]); - dp_neo[v] = abs(v - lines[i]) + best; - } - best = INT_MAX; - for(int v=lines[i]; v<=V; ++v) { - best = min(best, dp[v]); - dp_neo[v] = abs(v - lines[i]) + best; - } - dp.swap(dp_neo); - } - return dp[0] + N-1; - } -}; - -// BEGIN CUT HERE -#include -double start_time; string timer() - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } -template ostream& operator<<(ostream& os, const vector& v) - { os << "{ "; - for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } -void verify_case(const int& Expected, const int& Received) { - bool ok = (Expected == Received); - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); -#define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} -int main(){ - -CASE(0) - int lines_[] = { 3, 2, 3 }; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 6; -END -CASE(1) - int lines_[] = { 0 }; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 0; -END -CASE(2) - int lines_[] = { 1, 2, 4 } -; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 6; -END -CASE(3) - int lines_[] = { 250, 105, 155, 205, 350 } -; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 499; -END -CASE(4) -int lines_[] = {0}; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 0; -END -CASE(5) -int lines_[] = {1}; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 1; -END -CASE(5) - int lines_[] = {10}; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 10; -END -CASE(5) - int lines_[] = {10,10}; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 11; -END -CASE(5) - 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}; - vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); - int _ = 1000049; -END - -} -// END CUT HERE ADDED SRM/499/1B.cpp Index: SRM/499/1B.cpp ================================================================== --- SRM/499/1B.cpp +++ SRM/499/1B.cpp @@ -0,0 +1,104 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +class WhiteSpaceEditing { public: + int getMinimum(vector lines) + { + set slen(lines.begin(), lines.end()); + slen.insert(0); + + vector len(slen.begin(), slen.end()); + memo.assign(lines.size()*(lines.size()+1)*len.size(), -1); + return rec(lines, 0, lines.size(), len, 0) + (lines.size()-1); + } + + vector memo; + int rec(const vector& lines, int s, int e, + const vector& len, int cur_len) { + if(s+1 == e) + return abs(lines[s] - len[cur_len]); + + int key = (s*(lines.size()+1)+e)*len.size()+cur_len; + if(memo[key] != -1) + return memo[key]; + + int result = 0x1fffffff; + for(int base_len=0; base_len +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} +int main(){ + +CASE(0) + int lines_[] = { 3, 2, 3 }; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 6; +END +CASE(1) + int lines_[] = { 0 }; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 0; +END +CASE(2) + int lines_[] = { 1, 2, 4 } +; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 6; +END +CASE(3) + int lines_[] = { 250, 105, 155, 205, 350 } +; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 499; +END +/* +CASE(4) + int lines_[] = ; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = ; +END +CASE(5) + int lines_[] = ; + vector lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/555-U/1A.cpp Index: SRM/555-U/1A.cpp ================================================================== --- SRM/555-U/1A.cpp +++ SRM/555-U/1A.cpp @@ -0,0 +1,116 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +class CuttingBitString { public: + static const int INF = 999; + + int getmin(string S) + { + LL v = 1; + set good; + for(LL v=1; v<(1LL<<60); v*=5) { + cerr << bin(v) << endl; + good.insert(bin(v)); + } + + int s = best(S, good, 0, S.size()); + return s>=INF ? -1 : s; + } + + map, int> memo; + int best(const string& S, const set& good, int s, int e) + { + pair key(s,e); + if(memo.count(key)) + return memo[key]; + + if( good.count(S.substr(s, e-s)) ) + return memo[key] = 1; + int score = INF; + for(int m=s+1; m+1<=e; ++m) + { + int x = best(S, good, s, m); + int y = best(S, good, m, e); + score = min(score, x+y); + } + return memo[key] = score; + } + + string bin(LL v) + { + string s; + for(; v; v>>=1) + s += (v&1 ? '1' : '0'); + reverse(s.begin(), s.end()); + return s; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, CuttingBitString().getmin(S));} +int main(){ + +CASE(3) + string S = "110011011"; + int _ = 3; +END +CASE(0) + string S = "101101101"; + int _ = 3; +END +CASE(1) + string S = "1111101"; + int _ = 1; +END +CASE(2) + string S = "00000"; + int _ = -1; +END +CASE(4) + string S = "1000101011"; + int _ = -1; +END +CASE(5) + string S = "111011100110101100101110111"; + int _ = 5; +END +CASE(6) + string S = "11111111111111111111111111111111111111111111111111"; + int _ = -999; +END +CASE(7) + string S = "1101100011010111001001101011011100010111011110101"; + int _ = 1; +END +} +// END CUT HERE ADDED SRM/555-U/1B.cpp Index: SRM/555-U/1B.cpp ================================================================== --- SRM/555-U/1B.cpp +++ SRM/555-U/1B.cpp @@ -0,0 +1,161 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +static const unsigned MODVAL = 555555555; +struct mint +{ + unsigned val; + mint():val(0){} + mint(int x):val(x%MODVAL) {} + mint(unsigned x):val(x%MODVAL) {} + mint(LL x):val(x%MODVAL) {} +}; +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } +mint operator+(mint x, mint y) { return x+=y; } +mint operator-(mint x, mint y) { return x-=y; } +mint operator*(mint x, mint y) { return x*=y; } +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } + +vector< vector > CP_; +mint C(LL n, LL k) { + while( CP_.size() <= n ) { + int nn = CP_.size(); + CP_.push_back(vector(nn+1,1)); + for(int kk=1; kk xx(W+1), yy(H+1); + for(int x=0; x<=W; ++x) + xx[x] = subProblem(W, Ccount, x); + for(int y=0; y<=H; ++y) + yy[y] = subProblem(H, Rcount, y); + + mint cnt = 0; + for(int x=0; x<=W; ++x) + for(int y=0; y<=H; ++y) + if( x*(H-y)+(W-x)*y == S ) + cnt += xx[x]*yy[y]; + return cnt.val; + } + + mint subProblem(int Z, int T, int k) + { + // Z objects + // T flips + // k of them flipped odd # of times + // Z-k even + if( T < k ) + return 0; + T -= k; + if( T%2 != 0 ) + return 0; + T /= 2; + mint cc = C(Z, k); + // Z obj + // T flips + return cc * C(T+Z-1, Z-1); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, XorBoard().count(H, W, Rcount, Ccount, S));} +int main(){ + +CASE(0) + int H = 2; + int W = 2; + int Rcount = 2; + int Ccount = 2; + int S = 4; + int _ = 4; +END +CASE(1) + int H = 2; + int W = 2; + int Rcount = 0; + int Ccount = 0; + int S = 1; + int _ = 0; +END +CASE(2) + int H = 10; + int W = 20; + int Rcount = 50; + int Ccount = 40; + int S = 200; + int _ = 333759825; +END +CASE(3) + int H = 1200; + int W = 1000; + int Rcount = 800; + int Ccount = 600; + int S = 4000; + int _ = 96859710; +END +CASE(4) + int H = 555; + int W = 555; + int Rcount = 555; + int Ccount = 555; + int S = 5550; + int _ = 549361755; +END +CASE(5) + int H = 1555; + int W = 1555; + int Rcount = 755; + int Ccount = 755; + int S = 555555; + int _ = -1; +END +/* +CASE(6) + int H = ; + int W = ; + int Rcount = ; + int Ccount = ; + int S = ; + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/555-U/1C-U.cpp Index: SRM/555-U/1C-U.cpp ================================================================== --- SRM/555-U/1C-U.cpp +++ SRM/555-U/1C-U.cpp @@ -0,0 +1,221 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +template +struct DP2 +{ + const int N1, N2; + vector data; + DP2(int N1, int N2, const T& t = T()) + : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); } + T& operator()(int i1, int i2) + { return data[ (i1*N2)+i2 ]; } + void swap(DP2& rhs) + { data.swap(rhs.data); } +}; + +class MapGuessing { public: + long long countPatterns(string goal, vector code_) + { + string code = accumulate(code_.begin(), code_.end(), string("")); + deque pattern(1, '?'); + int head = 0; + for(int i=0; i': + head++; + if(head==pattern.size()) + pattern.push_back('?'); + break; + } + return solve(goal, string(pattern.begin(), pattern.end())); + } + + LL solve(const string& G, const string& P) + { + if(P.size() > G.size()) + return 0; + + int N = P.size(); + vector< vector > DFA(N, vector(2)); + for(int i=0; i=0; --k) + if( match(P.substr(0, k), P.substr(i-k, k)) + && match(P[k], nega(P[i])) ) { + fail = k; + break; + } + + if(P[i]=='0') + { + DFA[i][0] = i+1; + DFA[i][1] = fail; + } + else if(P[i]=='1') + { + DFA[i][0] = fail; + DFA[i][1] = i+1; + } + else + { + DFA[i][0] = i+1; + DFA[i][1] = i+1; + } + } + + LL total = 0; + for(int s=0; s+P.size()<=G.size(); ++s) + { + LL v = subProblem(s, G, s+P.size(), DFA, N); + total += v; + } + return total; + } + + char nega(char c) { return c=='?' ? c : c=='0' ? '1' : '0'; } + bool match(char a, char b) { + return a=='?' || b=='?' || a==b; + } + bool match(const string& a, const string& b) { + for(int i=0; i >& DFA, int Q) + { + DP2 dp(M+1, Q+1); + dp(0, 0) = 1; + for(int i=0; i=i || G[i]=='0') + dp(i+1, DFA[q][0]) += dp(i,q); + if(s>=i || G[i]=='1') + dp(i+1, DFA[q][1]) += dp(i,q); + } + return dp(M, Q); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, MapGuessing().countPatterns(goal, code));} +int main(){ + +CASE(0) + string goal = "000"; + string code_[] = {"0"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 4LL; +END +CASE(1) + string goal = "001"; + string code_[] = {"0>1"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 5LL; +END +CASE(2) + string goal = "000"; + string code_[] = {"1>1>1"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 1LL; +END +CASE(3) + string goal = "11001"; + string code_[] = {">><<<<><<"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 0LL; +END +CASE(4) + string goal = "1000101011"; + string code_[] = {"1<<0>>0>1"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 22LL; +END +CASE(5) + string goal = "00000010000000000000000000000000"; + string code_[] = {"><>>0<0<>>1>0><>", "<<0>>0<>><0>0>>><><", ">>>0<>", ">0><>>>>0<<><>>0>>>0<0>>0>"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 13601LL; +END +CASE(6) + string goal = "11100011010111111010100100110001101"; + string code_[] = {"11111111111111111111" +,"1<><><><><><><><><>1" +,"1<>000>000><0<><0<>1" +,"1<0<><>0><0<00>00<>1" +,"1<>00<>000><0<0<0<>1" +,"1<><>0>0><0<0<><0<>1" +,"1<000<>0><0<0<><0<>1" +,"1<><><><><><><><><>1" +,"1<>000><000<>000><>1" +,"1<>0><><0<><>0><><>1" +,"1<>000><000<>000><>1" +,"1<><>0><><0<><>0><>1" +,"1<>000><000<>000><>1" +,"1<><><><><><><><><>1" +,"11111111111111111111"}; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = 90LL; +END +/* +CASE(7) + string goal = ; + string code_[] = ; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = LL; +END +CASE(8) + string goal = ; + string code_[] = ; + vector code(code_, code_+sizeof(code_)/sizeof(*code_)); + long long _ = LL; +END + */ +} +// END CUT HERE Index: lib/graph/scc.cpp ================================================================== --- lib/graph/scc.cpp +++ lib/graph/scc.cpp @@ -4,11 +4,11 @@ // O(E) // // Verified by // - SRM 499 Div1 LV3 // -// Using "Spagetthi Source"'s one path algorithm +// Using "Spagetthi Source"'s one pass algorithm //------------------------------------------------------------- template class IdGen {