Overview
| SHA1 Hash: | 0048d1d21b5aeb03572dd0adc2b7575cc5cc6df4 |
|---|---|
| Date: | 2013-11-01 14:13:26 |
| User: | kinaba |
| Comment: | 594 |
| 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/594-U/1A.cpp version [77245bfe6ee79be3]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class AstronomicalRecords { public: > 23 int minimalPlanets(vector <int> A, vector <int> B) > 24 { > 25 int best = A.size() + B.size(); > 26 for(int i=0; i<A.size(); ++i) > 27 for(int k=0; k<B.size(); ++k) > 28 { > 29 int score = 1; > 30 { > 31 vector<LL> AA, BB; > 32 for(int x=0; x<i; ++x) AA.push_back(LL(A[x])*B[k > 33 for(int x=0; x<k; ++x) BB.push_back(LL(B[x])*A[i > 34 score += AA.size()+BB.size()-lcs(AA, BB); > 35 } > 36 { > 37 vector<LL> AA, BB; > 38 for(int x=i+1; x<A.size(); ++x) AA.push_back(LL( > 39 for(int x=k+1; x<B.size(); ++x) BB.push_back(LL( > 40 score += AA.size()+BB.size()-lcs(AA, BB); > 41 } > 42 best = min(best, score); > 43 } > 44 return best; > 45 } > 46 > 47 int lcs(vector<LL> A, vector<LL> B) > 48 { > 49 vector< vector<int> > dp(A.size()+1, vector<int>(B.size()+1)); > 50 > 51 for(int i=0; i<A.size(); ++i) > 52 for(int k=0; k<B.size(); ++k) > 53 { > 54 int z = max(dp[i][k+1], dp[i+1][k]); > 55 if(A[i] == B[k]) > 56 z = max(z, dp[i][k]+1); > 57 dp[i+1][k+1] = z; > 58 } > 59 return dp[A.size()][B.size()]; > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, AstronomicalRecords().minimalPlanets(A, B));} > 77 int main(){ > 78 > 79 CASE(0) > 80 int A_[] = {1,2,1,2,1}; > 81 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 82 int B_[] = {2,1,2,1,2}; > 83 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 84 int _ = 6; > 85 END > 86 CASE(1) > 87 int A_[] = {1,2,3,4}; > 88 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 89 int B_[] = {2,4,6,8}; > 90 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 91 int _ = 4; > 92 END > 93 CASE(2) > 94 int A_[] = {2,3,2,3,2,3,2}; > 95 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 96 int B_[] = {600,700,600,700,600,700,600}; > 97 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 98 int _ = 10; > 99 END > 100 CASE(3) > 101 int A_[] = {1,2,3,4,5,6,7,8,9}; > 102 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 103 int B_[] = {6,7,8,9,10,11,12}; > 104 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 105 int _ = 12; > 106 END > 107 CASE(4) > 108 int A_[] = {100000000,200000000}; > 109 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 110 int B_[] = {200000000,100000000}; > 111 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 112 int _ = 3; > 113 END > 114 CASE(5) > 115 int A_[] = {7,14,7,14,7,1}; > 116 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 117 int B_[] = {10,5,10,5,10,1}; > 118 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 119 int _ = 8; > 120 END > 121 /* > 122 CASE(6) > 123 int A_[] = ; > 124 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 125 int B_[] = ; > 126 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 127 int _ = ; > 128 END > 129 */ > 130 } > 131 // END CUT HERE
Added SRM/594-U/1B.cpp version [e434289117e0d74f]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 typedef int vert; > 23 typedef vert edge; > 24 typedef vector<edge> edges; > 25 typedef vector<edges> graph; > 26 > 27 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 28 { > 29 for(int i=0; i<G[v].size(); ++i) { > 30 vert u = G[v][i]; > 31 if( visited[u] ) continue; > 32 visited[u] = true; > 33 > 34 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 35 { matchTo[v]=u, matchTo[u]=v; return true; } > 36 } > 37 return false; > 38 } > 39 > 40 template<int NV> > 41 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 42 // only left->right edges are used during computation > 43 { > 44 vector<vert> matchTo(G.size(), -1); > 45 int ans = 0; > 46 for(vert v=0; v<L; ++v) { > 47 bool visited[NV] = {}; > 48 if( augment(G, v, matchTo, visited) ) > 49 ++ans; > 50 } > 51 return ans; > 52 } > 53 > 54 class FoxAndGo3 { public: > 55 int maxEmptyCells(vector <string> board) > 56 { > 57 const int N = board.size(); > 58 > 59 vector< vector<int> > ID(N, vector<int>(N)); > 60 int Nblank=0, Nwhite=0; > 61 for(int y=0; y<N; ++y) > 62 for(int x=0; x<N; ++x) > 63 if(board[y][x]=='.') > 64 Nblank++; > 65 else if(board[y][x]=='o') > 66 Nwhite++; > 67 int IDblank = 0, IDwhite = Nblank; > 68 for(int y=0; y<N; ++y) > 69 for(int x=0; x<N; ++x) > 70 if(board[y][x]=='.') > 71 ID[y][x] = IDblank++; > 72 else if(board[y][x]=='o') > 73 ID[y][x] = IDwhite++; > 74 > 75 const int dy[] = {-1,+1,0,0}; > 76 const int dx[] = {0,0,-1,+1}; > 77 graph G(Nblank+Nwhite); > 78 for(int y=0; y<N; ++y) > 79 for(int x=0; x<N; ++x) > 80 if(board[y][x]=='o') > 81 for(int d=0; d<4; ++d) { > 82 int yy = y+dy[d], xx = x+dx[d]; > 83 if(0<=yy&&yy<N&&0<=xx&&xx<N&&board[yy][x > 84 G[ID[yy][xx]].push_back(ID[y][x] > 85 } > 86 return Nblank + Nwhite - biMatch<2500>(G, Nblank); > 87 } > 88 }; > 89 > 90 // BEGIN CUT HERE > 91 #include <ctime> > 92 double start_time; string timer() > 93 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 94 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 95 { os << "{ "; > 96 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 97 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 98 void verify_case(const int& Expected, const int& Received) { > 99 bool ok = (Expected == Received); > 100 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 101 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 102 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 103 #define END verify_case(_, FoxAndGo3().maxEmptyCells(board));} > 104 int main(){ > 105 > 106 CASE(0) > 107 string board_[] = {"o.o", > 108 ".o.", > 109 "o.o"}; > 110 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 111 int _ = 5; > 112 END > 113 CASE(1) > 114 string board_[] = {"...", > 115 ".o.", > 116 "..."} > 117 ; > 118 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 119 int _ = 8; > 120 END > 121 CASE(2) > 122 string board_[] = {"xxxxx", > 123 "xxoxx", > 124 "xo.ox", > 125 "xxoxx", > 126 "xxxxx"} > 127 ; > 128 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 129 int _ = 4; > 130 END > 131 CASE(3) > 132 string board_[] = {".xox.", > 133 ".o.ox", > 134 "x.o.o", > 135 "ox.ox", > 136 ".ox.."} > 137 ; > 138 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 139 int _ = 12; > 140 END > 141 CASE(4) > 142 string board_[] = {"o.o.o", > 143 ".ox..", > 144 "oxxxo", > 145 "..x..", > 146 "o.o.o"} > 147 ; > 148 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 149 int _ = 12; > 150 END > 151 CASE(5) > 152 string board_[] = {"...", > 153 "...", > 154 "..."}; > 155 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 156 int _ = 9; > 157 END > 158 /* > 159 CASE(6) > 160 string board_[] = ; > 161 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 162 int _ = ; > 163 END > 164 CASE(7) > 165 string board_[] = ; > 166 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 167 int _ = ; > 168 END > 169 */ > 170 } > 171 // END CUT HERE