Overview
| SHA1 Hash: | 2adfb7dfc08f5c892a58af78d3141fb6487d712f |
|---|---|
| Date: | 2013-04-20 15:27:04 |
| User: | kinaba |
| Comment: | 576 |
| 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/576-U/1A.cpp version [8b5e78cefb5c79ec]
> 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 ArcadeManao { public: > 23 int shortestLadder(vector <string> level, int coinRow, int coinColumn) > 24 { > 25 for(int L=0; L<=level.size(); ++L) > 26 if(can(level, coinRow-1, coinColumn-1, L)) > 27 return L; > 28 return level.size(); > 29 } > 30 > 31 bool can(vector <string> level, int Cy, int Cx, int L) > 32 { > 33 int H = level.size(); > 34 int W = level[0].size(); > 35 typedef pair<int,int> point; > 36 set<point> V; > 37 queue<point> Q; > 38 Q.push(point(H-1, 0)); > 39 V.insert(Q.front()); > 40 while(!Q.empty()) { > 41 point p = Q.front(); > 42 int y=p.first, x=p.second; > 43 Q.pop(); > 44 if(y==Cy && x==Cx) > 45 return true; > 46 vector<point> cand; > 47 cand.push_back(point(y,x-1)); > 48 cand.push_back(point(y,x+1)); > 49 for(int dy=-L; dy<=+L; ++dy) > 50 cand.push_back(point(y+dy, x)); > 51 > 52 for(int i=0; i<cand.size(); ++i) { > 53 int yy = cand[i].first; > 54 int xx = cand[i].second; > 55 point pp(yy,xx); > 56 if(0<=yy&&yy<H&&0<=xx&&xx<W&&level[y][x]=='X'&&! > 57 Q.push(pp); > 58 V.insert(pp); > 59 } > 60 } > 61 } > 62 return false; > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const int& Expected, const int& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, ArcadeManao().shortestLadder(level, coinRow, coi > 80 int main(){ > 81 > 82 CASE(0) > 83 string level_[] = {"XXXX....", > 84 "...X.XXX", > 85 "XXX..X..", > 86 "......X.", > 87 "XXXXXXXX"}; > 88 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 89 int coinRow = 2; > 90 int coinColumn = 4; > 91 int _ = 2; > 92 END > 93 CASE(1) > 94 string level_[] = {"XXXX", > 95 "...X", > 96 "XXXX"}; > 97 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 98 int coinRow = 1; > 99 int coinColumn = 1; > 100 int _ = 1; > 101 END > 102 CASE(2) > 103 string level_[] = {"..X..", > 104 ".X.X.", > 105 "X...X", > 106 ".X.X.", > 107 "..X..", > 108 "XXXXX"}; > 109 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 110 int coinRow = 1; > 111 int coinColumn = 3; > 112 int _ = 4; > 113 END > 114 CASE(3) > 115 string level_[] = {"X"}; > 116 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 117 int coinRow = 1; > 118 int coinColumn = 1; > 119 int _ = 0; > 120 END > 121 CASE(4) > 122 string level_[] = {"XXXXXXXXXX", > 123 "...X......", > 124 "XXX.......", > 125 "X.....XXXX", > 126 "..XXXXX..X", > 127 ".........X", > 128 ".........X", > 129 "XXXXXXXXXX"}; > 130 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 131 int coinRow = 1; > 132 int coinColumn = 1; > 133 int _ = 2; > 134 END > 135 CASE(5) > 136 string level_[] = { > 137 "XXXXXXXXXXXXXXX", > 138 "..............X", > 139 "..............X", > 140 "..............X", > 141 "XXXXXXXXXXXXXXX", > 142 }; > 143 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 144 int coinRow = 1; > 145 int coinColumn = 1; > 146 int _ = 1; > 147 END > 148 /* > 149 CASE(6) > 150 string level_[] = ; > 151 vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 152 int coinRow = ; > 153 int coinColumn = ; > 154 int _ = ; > 155 END > 156 */ > 157 } > 158 // END CUT HERE
Added SRM/576-U/1B-U.cpp version [8dbea917ed98c3a1]
> 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 = 1000000009; > 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 template<typename T> > 39 struct DP4x > 40 { > 41 int N1, N2, N3, N4; > 42 vector<T> data; > 43 DP4x(int, int N2, int N3, int N4, const T& t = T()) > 44 : N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(d > 45 T& operator()(int i1, int i2, int i3, int i4) > 46 { i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } > 47 void swap(DP4x& rhs) > 48 { data.swap(rhs.data); } > 49 }; > 50 > 51 class TheExperiment { public: > 52 int countPlacements(vector <string> intensity, int M, int L, int A, int > 53 { > 54 string S = accumulate(intensity.begin(), intensity.end(), string > 55 int N = S.size(); > 56 > 57 vector<int> range_L, range_R; // [L,R) > 58 { > 59 vector<int> PS(N+1, 0); > 60 for(int i=0; i<N; ++i) > 61 PS[i+1] = PS[i] + (S[i]-'0'); > 62 for(int i=0; i<N; ++i) > 63 { > 64 int LL = PS[i]+A; > 65 int RR = PS[i]+B+1; > 66 range_L.push_back(lower_bound(PS.begin(), PS.end > 67 range_R.push_back(lower_bound(PS.begin(), PS.end > 68 //cerr<<i<<" ["<<range_L.back()<<"-"<<range_R.ba > 69 } > 70 } > 71 > 72 DP4x<mint> dp(M+1, N+1, M, 2); > 73 dp(0, 0, 0, 0) = 1; > 74 for(int i=0; i<M; ++i) > 75 { > 76 // Clear > 77 for(int x=0; x<=N; ++x) > 78 for(int rank=0; rank<M; ++rank) { > 79 for(int hami=0; hami<2; ++hami) { > 80 if(dp(i,x,rank,hami).val) > 81 cerr<<i<<" "<<x<<" "<<rank<<" "<<hami<<" : "<< d > 82 dp(i+1, x, rank, hami) = 0; > 83 } > 84 > 85 // DP > 86 for(int x=0; x<N; ++x) > 87 for(int rank=0; rank<=i; ++rank) > 88 for(int hami=0; hami<2; ++hami) > 89 { > 90 mint v = dp(i,x,rank,hami); > 91 if(v.val != 0) > 92 for(int y=range_L[x]; y<range_R[x]; ++y) > 93 { > 94 if(y-x < L) { > 95 if(hami) { > 96 for(int r=0; r<= > 97 dp(i+1, > 98 } else { > 99 } > 100 } else if(y-x == L) { > 101 if(hami) > 102 dp(i+1, y, i, 0) > 103 else > 104 dp(i+1, y, i, 0) > 105 } else { > 106 break; > 107 } > 108 } > 109 } > 110 } > 111 mint acc = 0; > 112 for(int rank=0; rank<M; ++rank) > 113 acc += dp(M, N, rank, 0); > 114 return acc.val; > 115 } > 116 }; > 117 > 118 // BEGIN CUT HERE > 119 #include <ctime> > 120 double start_time; string timer() > 121 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 122 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 123 { os << "{ "; > 124 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 125 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 126 void verify_case(const int& Expected, const int& Received) { > 127 bool ok = (Expected == Received); > 128 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 129 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 130 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 131 #define END verify_case(_, TheExperiment().countPlacements(intensity, M, L, > 132 int main(){ > 133 > 134 CASE(0) > 135 string intensity_[] = {"341156"}; > 136 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 137 int M = 3; > 138 int L = 3; > 139 int A = 6; > 140 int B = 10; > 141 int _ = 2; > 142 END > 143 CASE(1) > 144 string intensity_[] = {"999112999"}; > 145 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 146 int M = 2; > 147 int L = 4; > 148 int A = 21; > 149 int B = 30; > 150 int _ = 2; > 151 END > 152 CASE(2) > 153 string intensity_[] = {"111"}; > 154 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 155 int M = 2; > 156 int L = 2; > 157 int A = 2; > 158 int B = 3; > 159 int _ = 0; > 160 END > 161 CASE(3) > 162 string intensity_[] = {"59059", "110", "1132230231"}; > 163 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 164 int M = 1; > 165 int L = 5; > 166 int A = 10; > 167 int B = 20; > 168 int _ = 6; > 169 END > 170 CASE(4) > 171 string intensity_[] = {"111111111111111111111111", "11111111111111111111 > 172 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 173 int M = 12; > 174 int L = 8; > 175 int A = 4; > 176 int B = 2700; > 177 int _ = 418629948; > 178 END > 179 /* > 180 CASE(5) > 181 string intensity_[] = ; > 182 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 183 int M = ; > 184 int L = ; > 185 int A = ; > 186 int B = ; > 187 int _ = ; > 188 END > 189 CASE(6) > 190 string intensity_[] = ; > 191 vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/si > 192 int M = ; > 193 int L = ; > 194 int A = ; > 195 int B = ; > 196 int _ = ; > 197 END > 198 */ > 199 } > 200 // END CUT HERE