ADDED SRM/578-U/1A.cpp Index: SRM/578-U/1A.cpp ================================================================== --- SRM/578-U/1A.cpp +++ SRM/578-U/1A.cpp @@ -0,0 +1,228 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex<LD> CMP; + +static const unsigned MODVAL = 1000000007; +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; } +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } +mint operator/(mint x, mint y) { return x/=y; } + +vector<mint> FAC_(1,1); +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; } + +// nCk :: O(1) time, O(n^2) space. +vector< vector<mint> > CP_; +mint C(LL n, LL k) { + while( CP_.size() <= n ) { + int nn = CP_.size(); + CP_.push_back(vector<mint>(nn+1,1)); + for(int kk=1; kk<nn; ++kk) + CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; + } + return k<0 || n<k ? 0 : CP_[n][k]; +} + +struct UnionFind +{ + vector<int> uf, sz; + int nc; + + UnionFind(int N): uf(N), sz(N,1), nc(N) + { for(int i=0; i<N; ++i) uf[i] = i; } + int size() + { return nc; } + int size(int a) + { return sz[Find(a)]; } + int Find(int a) + { return uf[a]==a ? a : uf[a]=Find(uf[a]); } + bool Union(int a, int b) + { + a = Find(a); + b = Find(b); + if( a != b ) + { + if( sz[a] >= sz[b] ) swap(a, b); + uf[a] = b; + sz[b] += sz[a]; + --nc; + } + return (a!=b); + } +}; + +class GooseInZooDivOne { public: + int count(vector <string> field, int dist) + { + int H = field.size(); + int W = field[0].size(); + vector<pair<int,int> > b; + for(int y=0; y<H; ++y) + for(int x=0; x<W; ++x) + if(field[y][x] == 'v') + b.push_back(make_pair(y,x)); + + int N = b.size(); + UnionFind uf(N); + for(int i=0; i<N; ++i) + for(int k=i+1; k<N; ++k) { + int y = b[i].first; + int x = b[i].second; + int Y = b[k].first; + int X = b[k].second; + if(abs(y-Y)+abs(x-X) <= dist) + uf.Union(i, k); + } + + int num[2]={0,0}; + for(int i=0; i<N; ++i) + if(uf.Find(i) == i) + num[uf.size(i)%2] ++; + return solve(num[0], num[1]).val; + } + + mint solve(int ev, int od) + { + mint total = 0; + for(int k=0; k<=od; k+=2) + total += C(od, k); + return POW(2, ev) * total - 1; + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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(_, GooseInZooDivOne().count(field, dist));} +int main(){ + +CASE(0) + string field_[] = {"vvv"}; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = 0; + int _ = 3; +END +CASE(1) + string field_[] = {"."}; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = 100; + int _ = 0; +END +CASE(2) + string field_[] = {"vvv"}; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = 1; + int _ = 0; +END +CASE(3) + string field_[] = {"v.v..................v............................" +,".v......v..................v.....................v" +,"..v.....v....v.........v...............v......v..." +,".........vvv...vv.v.........v.v..................v" +,".....v..........v......v..v...v.......v..........." +,"...................vv...............v.v..v.v..v..." +,".v.vv.................v..............v............" +,"..vv.......v...vv.v............vv.....v.....v....." +,"....v..........v....v........v.......v.v.v........" +,".v.......v.............v.v..........vv......v....." +,"....v.v.......v........v.....v.................v.." +,"....v..v..v.v..............v.v.v....v..........v.." +,"..........v...v...................v..............v" +,"..v........v..........................v....v..v..." +,"....................v..v.........vv........v......" +,"..v......v...............................v.v......" +,"..v.v..............v........v...............vv.vv." +,"...vv......v...............v.v..............v....." +,"............................v..v.................v" +,".v.............v.......v.........................." +,"......v...v........................v.............." +,".........v.....v..............vv.................." +,"................v..v..v.........v....v.......v...." +,"........v.....v.............v......v.v............" +,"...........v....................v.v....v.v.v...v.." +,"...........v......................v...v..........." +,"..........vv...........v.v.....................v.." +,".....................v......v............v...v...." +,".....vv..........................vv.v.....v.v....." +,".vv.......v...............v.......v..v.....v......" +,"............v................v..........v....v...." +,"................vv...v............................" +,"................v...........v........v...v....v..." +,"..v...v...v.............v...v........v....v..v...." +,"......v..v.......v........v..v....vv.............." +,"...........v..........v........v.v................" +,"v.v......v................v....................v.." +,".v........v................................v......" +,"............................v...v.......v........." +,"........................vv.v..............v...vv.." +,".......................vv........v.............v.." +,"...v.............v.........................v......" +,"....v......vv...........................v........." +,"....vv....v................v...vv..............v.." +,".................................................." +,"vv........v...v..v.....v..v..................v...." +,".........v..............v.vv.v.............v......" +,".......v.....v......v...............v............." +,"..v..................v................v....v......" +,".....v.....v.....................v.v......v......."}; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = 3; + int _ = 898961330; +END +/* +CASE(4) + string field_[] = ; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = ; + int _ = ; +END +CASE(5) + string field_[] = ; + vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); + int dist = ; + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/578-U/1B-U.cpp Index: SRM/578-U/1B-U.cpp ================================================================== --- SRM/578-U/1B-U.cpp +++ SRM/578-U/1B-U.cpp @@ -0,0 +1,162 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex<LD> CMP; + +static const unsigned MODVAL = 1000000007; + +class WolfInZooDivOne { public: + int count(int N, vector <string> L_, vector <string> R_) + { + vector<int> L, R; + { + stringstream sin(accumulate(L_.begin(), L_.end(), string())); + for(int s; sin>>s;) L.push_back(s); + } + { + stringstream sin(accumulate(R_.begin(), R_.end(), string())); + for(int s; sin>>s;) R.push_back(s+1); + } + + set< pair<int,int> > LR; + for(int i=0; i<L.size(); ++i) + LR.insert(make_pair(L[i], R[i])); + + vector< pair<int,int> > LR_imp; + for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); ++it) { + bool important = true; + for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR.end(); ++kt) + if(it != kt && kt->first<=it->first && it->second<=kt->second) + important = false; + if(important) + LR_imp.push_back(*it); + } + + return solve(N, LR_imp); + } + + int solve(int N, const vector< pair<int,int> >& LR) + { + memo = vector<vector<vector<int> > >(N, + vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+1, -1))); + return rec(0, N, LR, 0, 0, 0, 0); + } + + vector<vector<vector<int> > > memo; + int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_of_past, int end_of_two, int end_of_one, + int end_of_zero) + { + if(i == N) + return 1; + int& me = memo[i][end_of_two][end_of_one]; + if(me != -1) + return me; + + int ez = end_of_zero; + while(ez<LR.size() && LR[ez].first<=i) + ++ez; + int ep = end_of_past; + while(ep<ez && LR[ep].second<=i) + ++ep; + + // do not place wolf at i. + int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_of_one), ez); + + // place wolf at i. + if(ep >= end_of_two) { + int e1 = max(ep, end_of_one); + int e2 = max(ep, end_of_two); + while(e2<e1 && i<LR[e2].second) + ++e2; + while(e1<ez && i<LR[e1].second) + ++e1; + total += rec(i+1, N, LR, ep, e2, e1, ez); + } + return me = (total % MODVAL); + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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(_, WolfInZooDivOne().count(N, L, R));} +int main(){ + +CASE(0) + int N = 5; + string L_[] = {"0"}; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = {"4"}; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = 16; +END +CASE(1) + int N = 5; + string L_[] = {"0 1"}; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = {"2 4"}; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = 21; +END +CASE(2) + int N = 10; + string L_[] = {"0 4 2 7"}; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = {"3 9 5 9"}; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = 225; +END +CASE(3) + int N = 100; + string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"}; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"}; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = 6419882; +END +/* +CASE(4) + int N = ; + string L_[] = ; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = ; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = ; +END +CASE(5) + int N = ; + string L_[] = ; + vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); + string R_[] = ; + vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); + int _ = ; +END +*/ +} +// END CUT HERE