Overview
| SHA1 Hash: | 6efd022c374b79ed1e098000e7099b46c921df97 |
|---|---|
| Date: | 2013-05-11 15:43:02 |
| User: | kinaba |
| Comment: | 578 |
| 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/578-U/1A.cpp version [7755a8c9ae69e1f9]
> 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 = 1000000007; > 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 > 38 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 40 mint operator/(mint x, mint y) { return x/=y; } > 41 > 42 vector<mint> FAC_(1,1); > 43 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 44 > 45 // nCk :: O(1) time, O(n^2) space. > 46 vector< vector<mint> > CP_; > 47 mint C(LL n, LL k) { > 48 while( CP_.size() <= n ) { > 49 int nn = CP_.size(); > 50 CP_.push_back(vector<mint>(nn+1,1)); > 51 for(int kk=1; kk<nn; ++kk) > 52 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 53 } > 54 return k<0 || n<k ? 0 : CP_[n][k]; > 55 } > 56 > 57 struct UnionFind > 58 { > 59 vector<int> uf, sz; > 60 int nc; > 61 > 62 UnionFind(int N): uf(N), sz(N,1), nc(N) > 63 { for(int i=0; i<N; ++i) uf[i] = i; } > 64 int size() > 65 { return nc; } > 66 int size(int a) > 67 { return sz[Find(a)]; } > 68 int Find(int a) > 69 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 70 bool Union(int a, int b) > 71 { > 72 a = Find(a); > 73 b = Find(b); > 74 if( a != b ) > 75 { > 76 if( sz[a] >= sz[b] ) swap(a, b); > 77 uf[a] = b; > 78 sz[b] += sz[a]; > 79 --nc; > 80 } > 81 return (a!=b); > 82 } > 83 }; > 84 > 85 class GooseInZooDivOne { public: > 86 int count(vector <string> field, int dist) > 87 { > 88 int H = field.size(); > 89 int W = field[0].size(); > 90 vector<pair<int,int> > b; > 91 for(int y=0; y<H; ++y) > 92 for(int x=0; x<W; ++x) > 93 if(field[y][x] == 'v') > 94 b.push_back(make_pair(y,x)); > 95 > 96 int N = b.size(); > 97 UnionFind uf(N); > 98 for(int i=0; i<N; ++i) > 99 for(int k=i+1; k<N; ++k) { > 100 int y = b[i].first; > 101 int x = b[i].second; > 102 int Y = b[k].first; > 103 int X = b[k].second; > 104 if(abs(y-Y)+abs(x-X) <= dist) > 105 uf.Union(i, k); > 106 } > 107 > 108 int num[2]={0,0}; > 109 for(int i=0; i<N; ++i) > 110 if(uf.Find(i) == i) > 111 num[uf.size(i)%2] ++; > 112 return solve(num[0], num[1]).val; > 113 } > 114 > 115 mint solve(int ev, int od) > 116 { > 117 mint total = 0; > 118 for(int k=0; k<=od; k+=2) > 119 total += C(od, k); > 120 return POW(2, ev) * total - 1; > 121 } > 122 }; > 123 > 124 // BEGIN CUT HERE > 125 #include <ctime> > 126 double start_time; string timer() > 127 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 128 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 129 { os << "{ "; > 130 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 131 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 132 void verify_case(const int& Expected, const int& Received) { > 133 bool ok = (Expected == Received); > 134 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 135 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 136 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 137 #define END verify_case(_, GooseInZooDivOne().count(field, dist));} > 138 int main(){ > 139 > 140 CASE(0) > 141 string field_[] = {"vvv"}; > 142 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 143 int dist = 0; > 144 int _ = 3; > 145 END > 146 CASE(1) > 147 string field_[] = {"."}; > 148 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 149 int dist = 100; > 150 int _ = 0; > 151 END > 152 CASE(2) > 153 string field_[] = {"vvv"}; > 154 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 155 int dist = 1; > 156 int _ = 0; > 157 END > 158 CASE(3) > 159 string field_[] = {"v.v..................v............................" > 160 ,".v......v..................v.....................v" > 161 ,"..v.....v....v.........v...............v......v..." > 162 ,".........vvv...vv.v.........v.v..................v" > 163 ,".....v..........v......v..v...v.......v..........." > 164 ,"...................vv...............v.v..v.v..v..." > 165 ,".v.vv.................v..............v............" > 166 ,"..vv.......v...vv.v............vv.....v.....v....." > 167 ,"....v..........v....v........v.......v.v.v........" > 168 ,".v.......v.............v.v..........vv......v....." > 169 ,"....v.v.......v........v.....v.................v.." > 170 ,"....v..v..v.v..............v.v.v....v..........v.." > 171 ,"..........v...v...................v..............v" > 172 ,"..v........v..........................v....v..v..." > 173 ,"....................v..v.........vv........v......" > 174 ,"..v......v...............................v.v......" > 175 ,"..v.v..............v........v...............vv.vv." > 176 ,"...vv......v...............v.v..............v....." > 177 ,"............................v..v.................v" > 178 ,".v.............v.......v.........................." > 179 ,"......v...v........................v.............." > 180 ,".........v.....v..............vv.................." > 181 ,"................v..v..v.........v....v.......v...." > 182 ,"........v.....v.............v......v.v............" > 183 ,"...........v....................v.v....v.v.v...v.." > 184 ,"...........v......................v...v..........." > 185 ,"..........vv...........v.v.....................v.." > 186 ,".....................v......v............v...v...." > 187 ,".....vv..........................vv.v.....v.v....." > 188 ,".vv.......v...............v.......v..v.....v......" > 189 ,"............v................v..........v....v...." > 190 ,"................vv...v............................" > 191 ,"................v...........v........v...v....v..." > 192 ,"..v...v...v.............v...v........v....v..v...." > 193 ,"......v..v.......v........v..v....vv.............." > 194 ,"...........v..........v........v.v................" > 195 ,"v.v......v................v....................v.." > 196 ,".v........v................................v......" > 197 ,"............................v...v.......v........." > 198 ,"........................vv.v..............v...vv.." > 199 ,".......................vv........v.............v.." > 200 ,"...v.............v.........................v......" > 201 ,"....v......vv...........................v........." > 202 ,"....vv....v................v...vv..............v.." > 203 ,".................................................." > 204 ,"vv........v...v..v.....v..v..................v...." > 205 ,".........v..............v.vv.v.............v......" > 206 ,".......v.....v......v...............v............." > 207 ,"..v..................v................v....v......" > 208 ,".....v.....v.....................v.v......v......."}; > 209 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 210 int dist = 3; > 211 int _ = 898961330; > 212 END > 213 /* > 214 CASE(4) > 215 string field_[] = ; > 216 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 217 int dist = ; > 218 int _ = ; > 219 END > 220 CASE(5) > 221 string field_[] = ; > 222 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 223 int dist = ; > 224 int _ = ; > 225 END > 226 */ > 227 } > 228 // END CUT HERE
Added SRM/578-U/1B-U.cpp version [65c638c38947b473]
> 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 = 1000000007; > 23 > 24 class WolfInZooDivOne { public: > 25 int count(int N, vector <string> L_, vector <string> R_) > 26 { > 27 vector<int> L, R; > 28 { > 29 stringstream sin(accumulate(L_.begin(), L_.end(), string > 30 for(int s; sin>>s;) L.push_back(s); > 31 } > 32 { > 33 stringstream sin(accumulate(R_.begin(), R_.end(), string > 34 for(int s; sin>>s;) R.push_back(s+1); > 35 } > 36 > 37 set< pair<int,int> > LR; > 38 for(int i=0; i<L.size(); ++i) > 39 LR.insert(make_pair(L[i], R[i])); > 40 > 41 vector< pair<int,int> > LR_imp; > 42 for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); > 43 bool important = true; > 44 for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR > 45 if(it != kt && kt->first<=it->first && it->secon > 46 important = false; > 47 if(important) > 48 LR_imp.push_back(*it); > 49 } > 50 > 51 return solve(N, LR_imp); > 52 } > 53 > 54 int solve(int N, const vector< pair<int,int> >& LR) > 55 { > 56 memo = vector<vector<vector<int> > >(N, > 57 vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+ > 58 return rec(0, N, LR, 0, 0, 0, 0); > 59 } > 60 > 61 vector<vector<vector<int> > > memo; > 62 int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_o > 63 int end_of_zero) > 64 { > 65 if(i == N) > 66 return 1; > 67 int& me = memo[i][end_of_two][end_of_one]; > 68 if(me != -1) > 69 return me; > 70 > 71 int ez = end_of_zero; > 72 while(ez<LR.size() && LR[ez].first<=i) > 73 ++ez; > 74 int ep = end_of_past; > 75 while(ep<ez && LR[ep].second<=i) > 76 ++ep; > 77 > 78 // do not place wolf at i. > 79 int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_o > 80 > 81 // place wolf at i. > 82 if(ep >= end_of_two) { > 83 int e1 = max(ep, end_of_one); > 84 int e2 = max(ep, end_of_two); > 85 while(e2<e1 && i<LR[e2].second) > 86 ++e2; > 87 while(e1<ez && i<LR[e1].second) > 88 ++e1; > 89 total += rec(i+1, N, LR, ep, e2, e1, ez); > 90 } > 91 return me = (total % MODVAL); > 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) > 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 > 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() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, WolfInZooDivOne().count(N, L, R));} > 109 int main(){ > 110 > 111 CASE(0) > 112 int N = 5; > 113 string L_[] = {"0"}; > 114 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 115 string R_[] = {"4"}; > 116 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 117 int _ = 16; > 118 END > 119 CASE(1) > 120 int N = 5; > 121 string L_[] = {"0 1"}; > 122 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 123 string R_[] = {"2 4"}; > 124 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 125 int _ = 21; > 126 END > 127 CASE(2) > 128 int N = 10; > 129 string L_[] = {"0 4 2 7"}; > 130 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 131 string R_[] = {"3 9 5 9"}; > 132 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 133 int _ = 225; > 134 END > 135 CASE(3) > 136 int N = 100; > 137 string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62" > 138 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 139 string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 "," > 140 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 141 int _ = 6419882; > 142 END > 143 /* > 144 CASE(4) > 145 int N = ; > 146 string L_[] = ; > 147 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 148 string R_[] = ; > 149 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 150 int _ = ; > 151 END > 152 CASE(5) > 153 int N = ; > 154 string L_[] = ; > 155 vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 156 string R_[] = ; > 157 vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 158 int _ = ; > 159 END > 160 */ > 161 } > 162 // END CUT HERE