Overview
| SHA1 Hash: | f6764c7ea73f3cf93e0af382a8a8e90a37a9056b |
|---|---|
| Date: | 2011-12-17 16:43:26 |
| User: | kinaba |
| Comment: | 526 |
| 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/526-U/1A.cpp version [3cb93565653b1303]
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 DucksAlignment { public: 29 + int minimumTime(vector <string> grid) 30 + { 31 + vector<int> xs, ys; 32 + for(int y=0; y<grid.size(); ++y) 33 + for(int x=0; x<grid[y].size(); ++x) 34 + if( grid[y][x] == 'o' ) 35 + { 36 + xs.push_back(x); 37 + ys.push_back(y); 38 + } 39 + sort(xs.begin(), xs.end()); 40 + sort(ys.begin(), ys.end()); 41 + return min(single(xs)+line(ys), line(xs)+single(ys)); 42 + } 43 + 44 + int single(const vector<int>& xs) 45 + { 46 + int mid = xs[xs.size()/2]; 47 + int sum = 0; 48 + for(int i=0; i<xs.size(); ++i) 49 + sum += abs(xs[i] - mid); 50 + return sum; 51 + } 52 + 53 + int line(const vector<int>& xs) 54 + { 55 + int best = xs.back() * xs.size(); 56 + for(int lb=0; lb<=xs.back(); ++lb) { 57 + int sum = 0; 58 + for(int i=0; i<xs.size(); ++i) 59 + sum += abs(xs[i] - (lb+i)); 60 + best = min(best, sum); 61 + } 62 + return best; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 77 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 78 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 79 +#define END verify_case(_, DucksAlignment().minimumTime(grid));} 80 +int main(){ 81 + 82 +CASE(0) 83 + string grid_[] = {".o", 84 + "o."}; 85 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 86 + int _ = 1; 87 +END 88 +CASE(1) 89 + string grid_[] = {".o...", 90 + "..o..", 91 + "....o"}; 92 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 93 + int _ = 3; 94 +END 95 +CASE(2) 96 + string grid_[] = {"o..........", 97 + "..o........", 98 + ".......o...", 99 + "...........", 100 + "...........", 101 + "...........", 102 + "........o..", 103 + "..........."}; 104 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 105 + int _ = 16; 106 +END 107 +CASE(3) 108 + string grid_[] = {".........", 109 + "....o....", 110 + "........."}; 111 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 112 + int _ = 0; 113 +END 114 +CASE(4) 115 + string grid_[] = {"...o..........................", 116 + "............................o.", 117 + ".o............................", 118 + "............o.................", 119 + ".................o............", 120 + "......................o.......", 121 + "......o.......................", 122 + "....o.........................", 123 + "...............o..............", 124 + ".......................o......", 125 + "...........................o..", 126 + ".......o......................"}; 127 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 128 + int _ = 99; 129 +END 130 +/* 131 +CASE(5) 132 + string grid_[] = ; 133 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 134 + int _ = ; 135 +END 136 +CASE(6) 137 + string grid_[] = ; 138 + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 139 + int _ = ; 140 +END 141 +*/ 142 +} 143 +// END CUT HERE
Added SRM/526-U/1B.cpp version [6420102b826df671]
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 +static const int INF = 0x3fffffff; 28 + 29 +class PrimeCompositeGame { public: 30 + int theOutcome(int N, int K) 31 + { 32 + enum {P, C}; 33 + 34 + // sieve 35 + vector< vector<bool> > is(2, vector<bool>(N+1, true)); 36 + is[P][0] = is[C][0] = is[P][1] = is[C][1] = false; 37 + for(int p=2; p<=N; ++p) { 38 + if( is[P][p] ) 39 + for(int q=p+p; q<=N; q+=p) 40 + is[P][q] = false; 41 + is[C][p] = !is[P][p]; 42 + } 43 + 44 + vector< vector<int> > score(2, vector<int>(N+1)); 45 + multiset<int> lastK[2]; 46 + for(int t=0; t<=N; ++t) { 47 + for(int me=0; me<2; ++me) 48 + if( lastK[1^me].empty() ) // no valid move. immediately lose. 49 + score[me][t] = 0; 50 + else if( *lastK[1^me].begin() > 0 ) // all move make opponent win. take the longest. 51 + score[me][t] = - (1 + *lastK[1^me].rbegin()); 52 + else // I can win. take the shortest. 53 + score[me][t] = (1 + abs(*--lastK[1^me].lower_bound(1))); 54 + // maintain last K scores. 55 + for(int me=0; me<2; ++me) { 56 + if( is[1^me][t] ) 57 + lastK[me].insert( score[me][t] ); 58 + if( t-K>=0 && is[1^me][t-K] ) 59 + lastK[me].erase(lastK[me].find(score[me][t-K])); 60 + } 61 + } 62 + return score[P][N]; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 77 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 78 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 79 +#define END verify_case(_, PrimeCompositeGame().theOutcome(N, K));} 80 +int main(){ 81 + 82 +CASE(0) 83 + int N = 3; 84 + int K = 2; 85 + int _ = 1; 86 +END 87 +CASE(1) 88 + int N = 58; 89 + int K = 1; 90 + int _ = 0; 91 +END 92 +CASE(2) 93 + int N = 30; 94 + int K = 3; 95 + int _ = -2; 96 +END 97 +CASE(3) 98 + int N = 6; 99 + int K = 3; 100 + int _ = 1; 101 +END 102 +CASE(4) 103 + int N = 526; 104 + int K = 58; 105 + int _ = 19; 106 +END 107 +CASE(5) 108 + int N = 474747; 109 + int K = 474747; 110 + int _ = 1; 111 +END 112 +/* 113 +CASE(6) 114 + int N = ; 115 + int K = ; 116 + int _ = ; 117 +END 118 +*/ 119 +} 120 +// END CUT HERE
Modified lib/graph/mincostFlow.cpp from [a86509e21e3c5ec5] to [4236b55037662c66].
1 1 //------------------------------------------------------------- 2 2 // MinCost-MaxFlow 3 3 // O(??) 4 4 // 5 5 // Verified by 6 6 // - SRM 487 Div2 LV3 7 7 // - SRM 491 Div1 LV3 8 +// - SRM 526 Div1 LV1 8 9 //------------------------------------------------------------- 9 10 10 11 #include <iostream> 11 12 #include <string> 12 13 #include <vector> 13 14 #include <map> 14 15 #include <queue> ................................................................................ 48 49 F[s][t] = f; 49 50 F[t][s] = 0; 50 51 } 51 52 52 53 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 53 54 { 54 55 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 55 - static const Cost COST_INF = 1e+300; // !!EDIT HERE!! 56 - static const Flow FLOW_INF = 0x7fffffff; 56 + static const Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!! 57 + static const Flow FLOW_INF = // 0x7fffffff; 57 58 58 59 Cost total_cost = 0; 59 60 Flow total_flow = 0; 60 61 vector<Cost> h(N, 0); // potential 61 62 for(Flow RF=FLOW_INF; RF>0; ) // residual flow 62 63 { 63 64 // Dijkstra -- find the min-cost path