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) > 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(_, 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. imme > 49 score[me][t] = 0; > 50 else if( *lastK[1^me].begin() > 0 ) // all move > 51 score[me][t] = - (1 + *lastK[1^me].rbegi > 52 else // I can win. take the shortest. > 53 score[me][t] = (1 + abs(*--lastK[1^me].l > 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] > 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) > 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(_, 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 // MinCost-MaxFlow 2 // MinCost-MaxFlow 3 // O(??) 3 // O(??) 4 // 4 // 5 // Verified by 5 // Verified by 6 // - SRM 487 Div2 LV3 6 // - SRM 487 Div2 LV3 7 // - SRM 491 Div1 LV3 7 // - SRM 491 Div1 LV3 > 8 // - SRM 526 Div1 LV1 8 //------------------------------------------------------------- 9 //------------------------------------------------------------- 9 10 10 #include <iostream> 11 #include <iostream> 11 #include <string> 12 #include <string> 12 #include <vector> 13 #include <vector> 13 #include <map> 14 #include <map> 14 #include <queue> 15 #include <queue> ................................................................................................................................................................................ 48 F[s][t] = f; 49 F[s][t] = f; 49 F[t][s] = 0; 50 F[t][s] = 0; 50 } 51 } 51 52 52 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 53 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 53 { 54 { 54 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 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 Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!! 56 static const Flow FLOW_INF = 0x7fffffff; | 57 static const Flow FLOW_INF = // 0x7fffffff; 57 58 58 Cost total_cost = 0; 59 Cost total_cost = 0; 59 Flow total_flow = 0; 60 Flow total_flow = 0; 60 vector<Cost> h(N, 0); // potential 61 vector<Cost> h(N, 0); // potential 61 for(Flow RF=FLOW_INF; RF>0; ) // residual flow 62 for(Flow RF=FLOW_INF; RF>0; ) // residual flow 62 { 63 { 63 // Dijkstra -- find the min-cost path 64 // Dijkstra -- find the min-cost path