Overview
| SHA1 Hash: | 81eb41d4bae0a8d4e0a28df6db3f9efa999bc2ca |
|---|---|
| Date: | 2012-02-18 19:39:59 |
| User: | kinaba |
| Comment: | 533 |
| 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/533-U/1A.cpp version [a610cb1c6934038d]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class CasketOfStar { public: > 29 int maxEnergy(vector <int> weight) > 30 { > 31 return rec(weight, 0, weight.size()-1); > 32 } > 33 > 34 map<pair<int,int>, int> memo; > 35 int rec(const vector<int>& w, int L, int R) > 36 { > 37 if( L+1 == R ) > 38 return 0; > 39 pair<int,int> key(L,R); > 40 if( memo.count(key) ) > 41 return memo[key]; > 42 int best = 0; > 43 for(int C=L+1; C<R; ++C) > 44 best = max(best, rec(w, L, C) + rec(w, C, R)); > 45 return memo[key] = best + w[L]*w[R]; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, CasketOfStar().maxEnergy(weight));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int weight_[] = {1,2,3,4}; > 67 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 68 int _ = 12; > 69 END > 70 CASE(1) > 71 int weight_[] = {100,2,1,3,100}; > 72 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 73 int _ = 10400; > 74 END > 75 CASE(2) > 76 int weight_[] = {2,2,7,6,90,5,9}; > 77 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 78 int _ = 1818; > 79 END > 80 CASE(3) > 81 int weight_[] = {477,744,474,777,447,747,777,474}; > 82 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 83 int _ = 2937051; > 84 END > 85 CASE(4) > 86 int weight_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; > 87 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 88 int _ = 13; > 89 END > 90 /* > 91 CASE(5) > 92 int weight_[] = ; > 93 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 94 int _ = ; > 95 END > 96 CASE(6) > 97 int weight_[] = ; > 98 vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)) > 99 int _ = ; > 100 END > 101 */ > 102 } > 103 // END CUT HERE
Added SRM/533-U/1B.cpp version [e5788b934fa2273e]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 struct UnionFind > 29 { > 30 vector<int> uf, sz; > 31 int nc; > 32 > 33 UnionFind(int N): uf(N), sz(N,1), nc(N) > 34 { for(int i=0; i<N; ++i) uf[i] = i; } > 35 int size() > 36 { return nc; } > 37 int Find(int a) > 38 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 39 bool Union(int a, int b) > 40 { > 41 a = Find(a); > 42 b = Find(b); > 43 if( a != b ) > 44 { > 45 if( sz[a] >= sz[b] ) swap(a, b); > 46 uf[a] = b; > 47 sz[b] += sz[a]; > 48 --nc; > 49 } > 50 return (a!=b); > 51 } > 52 }; > 53 > 54 class MagicBoard { public: > 55 string ableToUnlock(vector <string> board) > 56 { > 57 const int H = board.size(); > 58 const int W = board[0].size(); > 59 vector<int> deg(H+W); > 60 UnionFind uf(H*W); > 61 > 62 int num = 0; > 63 for(int y=0; y<H; ++y) > 64 for(int x=0; x<W; ++x) > 65 if( board[y][x]=='#' ) { > 66 deg[y]++; > 67 deg[H+x]++; > 68 num++; > 69 for(int yy=0; yy<H; ++yy) > 70 if( board[yy][x]=='#' ) > 71 uf.Union(y*W+x, yy*W+x); > 72 for(int xx=0; xx<W; ++xx) > 73 if( board[y][xx]=='#' ) > 74 uf.Union(y*W+x, y*W+xx); > 75 } > 76 int odd_y = 0, odd_x = 0; > 77 for(int y=0; y<H; ++y) > 78 odd_y += (deg[y]%2==1); > 79 for(int x=0; x<W; ++x) > 80 odd_x += (deg[H+x]%2==1); > 81 return (uf.size()==H*W-num+1 && odd_y+odd_x<=2 && odd_y<2 ? "YES > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const string& Expected, const string& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, MagicBoard().ableToUnlock(board));} > 99 int main(){ > 100 > 101 CASE(0) > 102 string board_[] = {"##", > 103 ".#"}; > 104 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 105 string _ = "YES"; > 106 END > 107 CASE(1) > 108 string board_[] = {"#.", > 109 ".#"}; > 110 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 111 string _ = "NO"; > 112 END > 113 CASE(2) > 114 string board_[] = {"##", > 115 "##", > 116 "##"}; > 117 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 118 string _ = "YES"; > 119 END > 120 CASE(3) > 121 string board_[] = {"###", > 122 "###", > 123 "###"}; > 124 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 125 string _ = "NO"; > 126 END > 127 CASE(4) > 128 string board_[] = {"###", > 129 "..#", > 130 "###", > 131 "#..", > 132 "###"}; > 133 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 134 string _ = "NO"; > 135 END > 136 CASE(5) > 137 string board_[] = {"................", > 138 ".######..######.", > 139 ".######..######.", > 140 ".##......##..##.", > 141 ".##......##..##.", > 142 ".######..######.", > 143 ".######..######.", > 144 ".....##..##..##.", > 145 ".....##..##..##.", > 146 ".######..######.", > 147 ".######..######.", > 148 "................"}; > 149 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 150 string _ = "YES"; > 151 END > 152 CASE(6) > 153 string board_[] = {"#"}; > 154 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 155 string _ = "YES"; > 156 END > 157 CASE(7) > 158 string board_[] = {".#"}; > 159 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 160 string _ = "YES"; > 161 END > 162 CASE(8) > 163 string board_[] = { > 164 "#################################################", > 165 "#################################################", > 166 "#################################################", > 167 "#################################################", > 168 "#################################################", > 169 "#################################################", > 170 "#################################################", > 171 "#################################################", > 172 "#################################################", > 173 "#################################################", > 174 "#################################################", > 175 "#################################################", > 176 "#################################################", > 177 "#################################################", > 178 "#################################################", > 179 "#################################################", > 180 "#################################################", > 181 "#################################################", > 182 "#################################################", > 183 "#################################################", > 184 "#################################################", > 185 "#################################################", > 186 "#################################################", > 187 "#################################################", > 188 "#################################################", > 189 "#################################################", > 190 "#################################################", > 191 "#################################################", > 192 "#################################################", > 193 "#################################################", > 194 "#################################################", > 195 "#################################################", > 196 "#################################################", > 197 "#################################################", > 198 "#################################################", > 199 "#################################################", > 200 "#################################################", > 201 "#################################################", > 202 "#################################################", > 203 "#################################################", > 204 "#################################################", > 205 "#################################################", > 206 "#################################################", > 207 "#################################################", > 208 "#################################################", > 209 "#################################################", > 210 "#################################################", > 211 "#################################################", > 212 "#################################################", > 213 "#################################################", > 214 }; > 215 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 216 string _ = "???"; > 217 END > 218 > 219 } > 220 // END CUT HERE