Overview
| SHA1 Hash: | fd58d23e5f1783eef07b5bb6edfa0f066c362f67 |
|---|---|
| Date: | 2012-12-12 11:39:32 |
| User: | kinaba |
| Comment: | 563 |
| 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/563/1A.cpp version [e2ad405452c3a39a]
> 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 FoxAndHandle { public: > 23 string lexSmallestName(string S) > 24 { > 25 string cur = ""; > 26 int p = 0; > 27 while(cur.size()*2<S.size()) { > 28 string next_best; > 29 int next_p = -1; > 30 for(int x=p; x<S.size(); ++x) > 31 if(possible(cur+S[x], x+1, S)) { > 32 if(next_p==-1 || next_best>cur+S[x]) > 33 next_best=cur+S[x], next_p=x+1; > 34 } > 35 cur = next_best; > 36 p = next_p; > 37 } > 38 return cur; > 39 } > 40 > 41 bool possible(const string& used, int x, const string& S) > 42 { > 43 int freq[26] = {0}; > 44 int pos[26] = {0}; > 45 int tot[26] = {0}; > 46 for(int i=0; i<used.size(); ++i) > 47 freq[used[i]-'a']++; > 48 for(int i=0; i<S.size(); ++i) { > 49 if(x<=i) > 50 pos[S[i]-'a']++; > 51 tot[S[i]-'a']++; > 52 } > 53 for(int c=0; c<26; ++c) > 54 if((freq[c]+pos[c])*2<tot[c] || freq[c]*2>tot[c]) > 55 return false; > 56 return true; > 57 } > 58 }; > 59 > 60 // BEGIN CUT HERE > 61 #include <ctime> > 62 double start_time; string timer() > 63 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 64 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 65 { os << "{ "; > 66 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 67 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 68 void verify_case(const string& Expected, const string& Received) { > 69 bool ok = (Expected == Received); > 70 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 71 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 72 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 73 #define END verify_case(_, FoxAndHandle().lexSmallestName(S));} > 74 int main(){ > 75 > 76 CASE(0) > 77 string S = "foxfox"; > 78 string _ = "fox"; > 79 END > 80 CASE(1) > 81 string S = "ccieliel"; > 82 string _ = "ceil"; > 83 END > 84 CASE(2) > 85 string S = "abaabbab"; > 86 string _ = "aabb"; > 87 END > 88 CASE(3) > 89 string S = "bbbbaaaa"; > 90 string _ = "bbaa"; > 91 END > 92 CASE(4) > 93 string S = "fedcbafedcba"; > 94 string _ = "afedcb"; > 95 END > 96 CASE(5) > 97 string S = "nodevillivedon"; > 98 string _ = "deilvon"; > 99 END > 100 /* > 101 CASE(6) > 102 string S = ; > 103 string _ = ; > 104 END > 105 CASE(7) > 106 string S = ; > 107 string _ = ; > 108 END > 109 */ > 110 } > 111 // END CUT HERE
Added SRM/563/1B.cpp version [99aafca057045ff1]
> 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 template<typename T> > 23 struct DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 class SpellCards { public: > 36 int maxDamage(vector <int> level, vector <int> damage) > 37 { > 38 static const int IMPOSSIBLE = -99999999; > 39 > 40 int N = level.size(); > 41 DP2<int> dp(N, N+1, IMPOSSIBLE); > 42 for(int w=1; w<=N; ++w) > 43 for(int s=0; s<N; ++s) { > 44 int L = level[s]; > 45 int D = damage[s]; > 46 > 47 DP2<int> ip(L+1, w, IMPOSSIBLE); > 48 ip(1,0) = D; > 49 for(int c=1; c<=L; ++c) > 50 for(int k=1; k<w; ++k) { > 51 int sk = (s+k) % N; > 52 > 53 int v = ip(c-1,k-1); > 54 for(int p=1; p<=k; ++p) { > 55 int sp = (s+p) % N; > 56 v = max(v, ip(c,p-1) + dp(sp, k-p+1)); > 57 } > 58 ip(c,k) = v; > 59 } > 60 > 61 dp(s,w) = ip(L, w-1); > 62 } > 63 > 64 int theBest = 0; > 65 for(int s=0; s<N; ++s) > 66 { > 67 vector<int> best(N+1); > 68 for(int k=0; k<N; ++k) { > 69 best[k+1] = best[k]; > 70 for(int p=0; p<=k; ++p) > 71 best[k+1] = max(best[k+1], best[p] + dp( > 72 } > 73 theBest = max(theBest, best[N]); > 74 } > 75 return theBest; > 76 } > 77 }; > 78 > 79 // BEGIN CUT HERE > 80 #include <ctime> > 81 double start_time; string timer() > 82 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 83 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 84 { os << "{ "; > 85 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 86 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 87 void verify_case(const int& Expected, const int& Received) { > 88 bool ok = (Expected == Received); > 89 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 90 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 91 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 92 #define END verify_case(_, SpellCards().maxDamage(level, damage));} > 93 int main(){ > 94 > 95 CASE(0) > 96 int level_[] = {1,1,1}; > 97 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 98 int damage_[] = {10,20,30}; > 99 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 100 int _ = 60; > 101 END > 102 CASE(1) > 103 int level_[] = {3,3,3}; > 104 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 105 int damage_[] = {10,20,30}; > 106 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 107 int _ = 30; > 108 END > 109 CASE(2) > 110 int level_[] = {4,4,4}; > 111 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 112 int damage_[] = {10,20,30}; > 113 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 114 int _ = 0; > 115 END > 116 CASE(3) > 117 int level_[] = {50,1,50,1,50}; > 118 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 119 int damage_[] = {10,20,30,40,50}; > 120 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 121 int _ = 60; > 122 END > 123 CASE(4) > 124 int level_[] = {2,1,1}; > 125 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 126 int damage_[] = {40,40,10}; > 127 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 128 int _ = 80; > 129 END > 130 CASE(5) > 131 int level_[] = {1,2,1,1,3,2,1}; > 132 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 133 int damage_[] = {10,40,10,10,90,40,10}; > 134 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 135 int _ = 170; > 136 END > 137 CASE(6) > 138 int level_[] = {1,2,2,3,1,4,2}; > 139 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 140 int damage_[] = {113,253,523,941,250,534,454}; > 141 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 142 int _ = 1918; > 143 END > 144 CASE(7) > 145 int level_[] = {4,8,50,24,4,32,6,39,3,2,4,4,39,39,10,3,42,36,38,18,6,18, > 146 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 147 int damage_[] = {8577,2855,8317,7176,295,7028,5317,7099,4642,29,2481,724 > 148 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 149 int _ = -2; > 150 END > 151 CASE(8) > 152 int level_[] = {25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25 > 153 vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); > 154 int damage_[] = {8577,2855,8317,7176,295,7028,5317,7099,4642,29,2481,724 > 155 vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)) > 156 int _ = -2; > 157 END > 158 } > 159 // END CUT HERE
Added SRM/563/1C.cpp version [a5241fc4c196a524]
> 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 38 > 39 class CoinsGame { public: > 40 int ways(vector <string> board) > 41 { > 42 map<pair<int,int>,int> ID; > 43 for(int y=0; y<board.size(); ++y) > 44 for(int x=0; x<board[0].size(); ++x) > 45 if(board[y][x]=='.') { > 46 int id = ID.size() + 1; > 47 ID[make_pair(y,x)] = id; > 48 } > 49 > 50 vector< vector<int> > G(ID.size()+1); > 51 G[0] = vector<int>(4, 0); > 52 > 53 int H = board.size(); > 54 int W = board[0].size(); > 55 for(int y=0; y<board.size(); ++y) > 56 for(int x=0; x<board[0].size(); ++x) > 57 if(board[y][x]=='.') > 58 { > 59 int dy[]={-1,+1,0,0}; > 60 int dx[]={0,0,-1,+1}; > 61 for(int d=0; d<4; ++d) > 62 { > 63 int yy=y+dy[d], xx=x+dx[d]; > 64 if(yy<0||H<=yy||xx<0||W<=xx) { > 65 // fell > 66 G[ID[make_pair(y,x)]].push_back(0); // 0 > 67 } > 68 else if(board[yy][xx]=='#') { > 69 // stop at yy-dy[d], xx-dx[d] > 70 G[ID[make_pair(y,x)]].push_back(ID[make_ > 71 } > 72 else { > 73 G[ID[make_pair(y,x)]].push_back(ID[make_ > 74 } > 75 } > 76 } > 77 return solve(G).val; > 78 } > 79 > 80 mint solve(vector< vector<int> >& G) > 81 { > 82 vector< vector<int> > set_buffer; > 83 set<int> active_sets; > 84 set<int> active_splitters; > 85 > 86 { > 87 set_buffer.push_back( vector<int>(1,0) ); > 88 vector<int> all; > 89 for(int v=1; v<G.size(); ++v) > 90 all.push_back(v); > 91 set_buffer.push_back(all); > 92 > 93 active_sets.insert(0); > 94 active_sets.insert(1); > 95 active_splitters.insert(0); > 96 } > 97 > 98 while(!active_splitters.empty()) > 99 { > 100 const vector<int>& splv = set_buffer[*active_splitters.b > 101 set<int> spl(splv.begin(), splv.end()); > 102 active_splitters.erase(active_splitters.begin()); > 103 > 104 for(int d=0; d<4; ++d) > 105 for(set<int>::iterator it=active_sets.begin(); it!=activ > 106 { > 107 int ii = *it++; > 108 const vector<int>& cur = set_buffer[ii]; > 109 vector<int> t, f; > 110 for(int k=0; k<cur.size(); ++k) > 111 (spl.count(G[cur[k]][d]) ? t : f).push_b > 112 if(!t.empty() && !f.empty()) > 113 { > 114 set_buffer.push_back(t); > 115 set_buffer.push_back(f); > 116 active_sets.insert(set_buffer.size()-2); > 117 active_sets.insert(set_buffer.size()-1); > 118 if(active_splitters.count(ii)) { > 119 active_splitters.insert(set_buff > 120 active_splitters.insert(set_buff > 121 } else { > 122 active_splitters.insert(t.size() > 123 } > 124 active_splitters.erase(ii); > 125 active_sets.erase(ii); > 126 } > 127 } > 128 } > 129 > 130 vector<int> es; > 131 for(set<int>::iterator it=active_sets.begin(); it!=active_sets.e > 132 if(*it) > 133 es.push_back(set_buffer[*it].size()); > 134 /* > 135 for(bool changed=true; changed;) > 136 { > 137 changed=false; > 138 for(int i=0; i<eqs.size(); ++i) if(!eqs[i].second && !de > 139 set<int> spl(eqs[i].first.begin(), eqs[i].first. > 140 eqs[i].second = true; > 141 for(int k=0; k<eqs.size(); ++k) > 142 for(int d=0; d<4; ++d) if(!dead[k]) { > 143 vector<int> t, f; > 144 for(vector<int>::iterator it=eqs[k].firs > 145 (spl.count(G[*it][d]) ? t : f).p > 146 if(!t.empty() && !f.empty()) { > 147 if(eqs[k].second) { > 148 eqs.push_back(make_pair( > 149 eqs.push_back(make_pair( > 150 dead.push_back(false); > 151 dead.push_back(false); > 152 changed = true; > 153 } else { > 154 eqs.push_back(make_pair( > 155 eqs.push_back(make_pair( > 156 dead.push_back(false); > 157 dead.push_back(false); > 158 changed = true; > 159 } > 160 dead[k] = true; > 161 } > 162 } > 163 } > 164 } > 165 > 166 vector<int> es; > 167 for(int i=1; i<eqs.size(); ++i) if(!dead[i]) > 168 es.push_back(eqs[i].first.size()); > 169 */ > 170 int sum = accumulate(es.begin(), es.end(), 0); > 171 mint x = POW(2, sum); > 172 for(int i=0; i<es.size(); ++i) > 173 x -= POW(2, es[i])-1; > 174 return x-1; > 175 } > 176 }; > 177 > 178 // BEGIN CUT HERE > 179 #include <ctime> > 180 double start_time; string timer() > 181 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 182 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 183 { os << "{ "; > 184 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 185 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 186 void verify_case(const int& Expected, const int& Received) { > 187 bool ok = (Expected == Received); > 188 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 189 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 190 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 191 #define END verify_case(_, CoinsGame().ways(board));} > 192 int main(){ > 193 > 194 CASE(0) > 195 string board_[] = {".."}; > 196 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 197 int _ = 1; > 198 END > 199 CASE(1) > 200 string board_[] = {"##.#", > 201 ".###", > 202 "###.", > 203 "#.##"}; > 204 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 205 int _ = 11; > 206 END > 207 CASE(2) > 208 string board_[] = {"####", > 209 "#..#", > 210 "#..#", > 211 "####"}; > 212 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 213 int _ = 0; > 214 END > 215 CASE(3) > 216 string board_[] = {"#.#.#"}; > 217 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 218 int _ = 0; > 219 END > 220 CASE(4) > 221 string board_[] = {"........", > 222 "........", > 223 "........", > 224 "........", > 225 "........", > 226 "........", > 227 "........", > 228 "........"}; > 229 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 230 int _ = 688856388; > 231 END > 232 CASE(5) > 233 string board_[] = {"........................................", "........ > 234 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 235 int _ = 150087966; > 236 END > 237 CASE(5) > 238 string board_[] = {"........................................", > 239 "........................................", > 240 "........................................", > 241 "........................................", > 242 "........................................", > 243 "........................................", > 244 "........................................", > 245 "........................................", > 246 "........................................", > 247 "........................................", > 248 "........................................", > 249 "........................................", > 250 "........................................", > 251 "........................................", > 252 "........................................", > 253 "........................................", > 254 "........................................", > 255 "........................................", > 256 "........................................", > 257 "........................................",}; > 258 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 259 int _ = 150087966; > 260 END > 261 CASE(5) > 262 string board_[] = {"........................................", > 263 "........................................", > 264 "........................................", > 265 "........................................", > 266 "........................................", > 267 "........................................", > 268 "........................................", > 269 "........................................", > 270 "........................................", > 271 "........................................", > 272 "........................................", > 273 "........................................", > 274 "........................................", > 275 "........................................", > 276 "........................................", > 277 "........................................", > 278 "........................................", > 279 "........................................", > 280 "........................................", > 281 "........................................", > 282 "........................................", > 283 "........................................", > 284 "........................................", > 285 "........................................", > 286 "........................................", > 287 "........................................", > 288 "........................................", > 289 "........................................", > 290 "........................................", > 291 "........................................", > 292 "........................................", > 293 "........................................", > 294 "........................................", > 295 "........................................", > 296 "........................................", > 297 "........................................", > 298 "........................................", > 299 "........................................", > 300 "........................................", > 301 "........................................", > 302 "........................................", > 303 "........................................", > 304 "........................................", > 305 "........................................", > 306 "........................................", > 307 "........................................", > 308 "........................................", > 309 "........................................", > 310 "........................................", > 311 "........................................", > 312 "........................................", > 313 "........................................", > 314 "........................................", > 315 "........................................", > 316 "........................................", > 317 "........................................", > 318 "........................................", > 319 "........................................", > 320 "........................................", > 321 "........................................", > 322 "........................................", > 323 "........................................", > 324 "........................................", > 325 "........................................", > 326 "........................................", > 327 "........................................", > 328 "........................................", > 329 "........................................", > 330 "........................................", > 331 "........................................", > 332 "........................................", > 333 "........................................", > 334 "........................................", > 335 "........................................", > 336 "........................................", > 337 "........................................", > 338 "........................................", > 339 "........................................", > 340 "........................................", > 341 "........................................",}; > 342 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 343 int _ = 150087966; > 344 END > 345 } > 346 // END CUT HERE