Overview
| SHA1 Hash: | be86f38991e476ee76c4780bcb85939eee77f1cb |
|---|---|
| Date: | 2013-09-07 14:10:05 |
| User: | kinaba |
| Comment: | 589 |
| 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/589-U/1A.cpp version [15460ab419ea2b8c]
> 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 struct UnionFind > 23 { > 24 vector<int> uf, sz; > 25 int nc; > 26 > 27 UnionFind(int N): uf(N), sz(N,1), nc(N) > 28 { for(int i=0; i<N; ++i) uf[i] = i; } > 29 int size() > 30 { return nc; } > 31 int size(int a) > 32 { return sz[Find(a)]; } > 33 int Find(int a) > 34 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 35 bool Union(int a, int b) > 36 { > 37 a = Find(a); > 38 b = Find(b); > 39 if( a != b ) > 40 { > 41 if( sz[a] >= sz[b] ) swap(a, b); > 42 uf[a] = b; > 43 sz[b] += sz[a]; > 44 --nc; > 45 } > 46 return (a!=b); > 47 } > 48 }; > 49 > 50 class GooseTattarrattatDiv1 { public: > 51 int getmin(string S) > 52 { > 53 UnionFind uf(128); > 54 > 55 map<char,int> time_for; > 56 for(int i=0; i<S.size(); ++i) > 57 { > 58 time_for[S[i]]++; > 59 uf.Union(S[i], S[S.size()-1-i]); > 60 } > 61 > 62 int total = 0; > 63 > 64 set<char> done; > 65 for(auto c : S) > 66 { > 67 if(done.count(c)) > 68 continue; > 69 > 70 int need = 0; > 71 int m = 0; > 72 for(auto d : S) > 73 if(uf.Find(c) == uf.Find(d)) { > 74 if(done.count(d)) > 75 continue; > 76 done.insert(d); > 77 need += time_for[d]; > 78 m = max(m, time_for[d]); > 79 } > 80 total += (need - m); > 81 } > 82 > 83 return total; > 84 } > 85 }; > 86 > 87 // BEGIN CUT HERE > 88 #include <ctime> > 89 double start_time; string timer() > 90 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 91 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 92 { os << "{ "; > 93 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 94 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 95 void verify_case(const int& Expected, const int& Received) { > 96 bool ok = (Expected == Received); > 97 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 98 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 99 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 100 #define END verify_case(_, GooseTattarrattatDiv1().getmin(S));} > 101 int main(){ > 102 > 103 CASE(0) > 104 string S = "geese"; > 105 int _ = 2; > 106 END > 107 CASE(1) > 108 string S = "tattarrattat"; > 109 int _ = 0; > 110 END > 111 CASE(2) > 112 string S = "xyyzzzxxx"; > 113 int _ = 2; > 114 END > 115 CASE(3) > 116 string S = "xrepayuyubctwtykrauccnquqfuqvccuaakylwlcjuyhyammag"; > 117 int _ = 11; > 118 END > 119 CASE(4) > 120 string S = "abaabb"; > 121 int _ = 3; > 122 END > 123 /* > 124 CASE(5) > 125 string S = ; > 126 int _ = ; > 127 END > 128 CASE(6) > 129 string S = ; > 130 int _ = ; > 131 END > 132 */ > 133 } > 134 // END CUT HERE
Added SRM/589-U/1B.cpp version [d52e6b2498cc7fe5]
> 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 GearsDiv1 { public: > 55 int getmin(string color, vector <string> graph) > 56 { > 57 vector<int> r, g, b; > 58 for(int i=0; i<color.size(); ++i) > 59 (color[i]=='R' ? r : color[i]=='G' ? g : b).push_back(i) > 60 > 61 int rg = calc(graph, r, g); > 62 int gb = calc(graph, g, b); > 63 int br = calc(graph, b, r); > 64 return min(rg, min(gb, br)); > 65 } > 66 > 67 int calc(const vector<string>& G, const vector<int>& A, const vector<int > 68 { > 69 if(A.empty() || B.empty()) > 70 return 0; > 71 > 72 graph gr(A.size() + B.size()); > 73 for(int a=0; a<A.size(); ++a) > 74 for(int b=0; b<B.size(); ++b) > 75 { > 76 if(G[A[a]][B[b]] == 'Y') > 77 gr[a].push_back(A.size()+b); > 78 } > 79 return biMatch<256>(gr, A.size()); > 80 } > 81 }; > 82 > 83 // BEGIN CUT HERE > 84 #include <ctime> > 85 double start_time; string timer() > 86 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 87 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 88 { os << "{ "; > 89 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 90 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 91 void verify_case(const int& Expected, const int& Received) { > 92 bool ok = (Expected == Received); > 93 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 94 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 95 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 96 #define END verify_case(_, GearsDiv1().getmin(color, graph));} > 97 int main(){ > 98 > 99 CASE(0) > 100 string color = "RGB"; > 101 string graph_[] = {"NYY","YNY","YYN"}; > 102 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 103 int _ = 1; > 104 END > 105 CASE(1) > 106 string color = "RGBR"; > 107 string graph_[] = {"NNNN","NNNN","NNNN","NNNN"}; > 108 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 109 int _ = 0; > 110 END > 111 CASE(2) > 112 string color = "RGBR"; > 113 string graph_[] = {"NYNN","YNYN","NYNY","NNYN"}; > 114 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 115 int _ = 1; > 116 END > 117 CASE(3) > 118 string color = "RRRRRGRRBGRRGBBGGGBRRRGBRGRRGG"; > 119 string graph_[] = {"NNNNNYNNNYNNYNNNYNNNNNNNNYNNYY", > 120 "NNNNNNNNYNNNYNYNNYNNNNYNNYNNYY", > 121 "NNNNNYNNNNNNNNNNNNYNNNNNNYNNNY", > 122 "NNNNNNNNNYNNYNNYYYNNNNYNNYNNNN", > 123 "NNNNNNNNNYNNYNNYYYNNNNYNNNNNNN", > 124 "YNYNNNYYYNNYNYYNNNNNYYNYNNYYNN", > 125 "NNNNNYNNNNNNNNNYYYNNNNYNNYNNYY", > 126 "NNNNNYNNNNNNNNNYNNNNNNNNNNNNYN", > 127 "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY", > 128 "YNNYYNNNYNNNNYYNNNYNYYNYNNNNNN", > 129 "NNNNNNNNNNNNYNNYNYNNNNYNNNNNNY", > 130 "NNNNNYNNNNNNYNNYYYNNNNNNNNNNYN", > 131 "YYNYYNNNYNYYNYYNNNYNYNNYNNNNNN", > 132 "NNNNNYNNNYNNYNNYYYNNNNYNNYNYYY", > 133 "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY", > 134 "NNNYYNYYYNYYNYYNNNYNYNNYYNYYNN", > 135 "YNNYYNYNYNNYNYYNNNYNNNNYYNNYNN", > 136 "NYNYYNYNYNYYNYYNNNNYYNNYYNYNNN", > 137 "NNYNNNNNNYNNYNNYYNNNNNYNNYNNNY", > 138 "NNNNNNNNNNNNNNNNNYNNNNYNNYNNNY", > 139 "NNNNNYNNNYNNYNNYNYNNNNYNNNNNYY", > 140 "NNNNNYNNNYNNNNNNNNNNNNYNNNNNNN", > 141 "NYNYYNYNYNYNNYYNNNYYYYNYYNYNNN", > 142 "NNNNNYNNNYNNYNNYYYNNNNYNNNNNNY", > 143 "NNNNNNNNNNNNNNNYYYNNNNYNNYNNYY", > 144 "YYYYNNYNYNNNNYYNNNYYNNNNYNYYNN", > 145 "NNNNNYNNNNNNNNNYNYNNNNYNNYNNYN", > 146 "NNNNNYNNNNNNNYNYYNNNNNNNNYNNYY", > 147 "YYNNNNYYYNNYNYYNNNNNYNNNYNYYNN", > 148 "YYYNNNYNYNYNNYYNNNYYYNNYYNNYNN"}; > 149 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 150 int _ = 3; > 151 END > 152 /* > 153 CASE(4) > 154 string color = ; > 155 string graph_[] = ; > 156 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 157 int _ = ; > 158 END > 159 CASE(5) > 160 string color = ; > 161 string graph_[] = ; > 162 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 163 int _ = ; > 164 END > 165 */ > 166 } > 167 // END CUT HERE
Added SRM/589-U/1C-U.cpp version [ea7a7045ff580752]
> 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 FlippingBitsDiv1 { public: > 23 int getmin(vector <string> Sv, int M) > 24 { > 25 string S = accumulate(Sv.begin(), Sv.end(), string()); > 26 vector< vector<int> > Z(M); > 27 for(int i=0; i<S.size(); ++i) > 28 Z[i%M].push_back(S[i]-'0'); > 29 > 30 int best = S.size(); > 31 if(M <= 16) > 32 { > 33 for(int mask=0; mask<(1<<M); ++mask) > 34 { > 35 vector<int> target(M); > 36 for(int i=0; i<M; ++i) > 37 target[i] = (mask & (1<<i) ? 1 : 0); > 38 best = min(best, solve1(Z, target, M)); > 39 } > 40 } > 41 else > 42 { > 43 int X = Z.back().size(); > 44 for(int mask=0; mask<(1<<X); ++mask) > 45 { > 46 vector<int> flip_idx; > 47 for(int i=0; i<X; ++i) > 48 if(mask & (1<<i)) > 49 flip_idx.push_back(i); > 50 best = min(best, solve2(Z, flip_idx, M)); > 51 } > 52 } > 53 return best; > 54 } > 55 > 56 int solve1(const vector<vector<int>>& Z, const vector<int>& T, int M) > 57 { > 58 const int X = Z.front().size(); > 59 vector<int> nc(X+1), fc(X+1); > 60 for(int y=0; y<M; ++y) > 61 { > 62 vector<int> ncy(X+1); > 63 vector<int> fcy(X+1); > 64 for(int x=0; x<X; ++x) { > 65 ncy[x+1] = ncy[x] + (x>=Z[y].size() ? 0 : (Z[y][ > 66 fcy[x+1] = fcy[x] + (x>=Z[y].size() ? 0 : (Z[y][ > 67 nc[x+1] += ncy[x+1]; > 68 fc[x+1] += fcy[x+1]; > 69 } > 70 } > 71 > 72 int INF = 999999; > 73 vector<vector<int>> dp(X+1, vector<int>(2)); > 74 enum {N, F}; > 75 dp[X][N] = INF; > 76 dp[X][F] = -1; > 77 for(int x=X-1; x>=0; --x) > 78 { > 79 dp[x][N] = INF; > 80 dp[x][F] = INF; > 81 for(int q=x+1; q<=X; ++q) { > 82 dp[x][N] = min(dp[x][N], 1+dp[q][F]+(nc[q]-nc[x] > 83 dp[x][F] = min(dp[x][F], 1+dp[q][N]+(fc[q]-fc[x] > 84 } > 85 } > 86 return min(dp[0][N], dp[0][F]); > 87 } > 88 > 89 int solve2(const vector<vector<int>>& Z, const vector<int>& flip_idx, in > 90 { > 91 return -178116; > 92 } > 93 }; > 94 > 95 // BEGIN CUT HERE > 96 #include <ctime> > 97 double start_time; string timer() > 98 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 99 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 100 { os << "{ "; > 101 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 102 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 103 void verify_case(const int& Expected, const int& Received) { > 104 bool ok = (Expected == Received); > 105 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, FlippingBitsDiv1().getmin(S, M));} > 109 int main(){ > 110 > 111 CASE(0) > 112 string S_[] = {"00111000"}; > 113 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 114 int M = 1; > 115 int _ = 2; > 116 END > 117 CASE(1) > 118 string S_[] = {"101100001101"}; > 119 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 120 int M = 3; > 121 int _ = 2; > 122 END > 123 CASE(2) > 124 string S_[] = {"11111111"}; > 125 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 126 int M = 4; > 127 int _ = 0; > 128 END > 129 CASE(3) > 130 string S_[] = {"1101001000"}; > 131 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 132 int M = 8; > 133 int _ = 1; > 134 END > 135 CASE(4) > 136 string S_[] = {"1","10","11","100","101","110"}; > 137 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 138 int M = 5; > 139 int _ = 4; > 140 END > 141 CASE(5) > 142 string S_[] = {"1001011000101010001111111110111011011100110001001"}; > 143 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 144 int M = 2; > 145 int _ = 16; > 146 END > 147 /* > 148 CASE(6) > 149 string S_[] = ; > 150 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 151 int M = ; > 152 int _ = ; > 153 END > 154 CASE(7) > 155 string S_[] = ; > 156 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 157 int M = ; > 158 int _ = ; > 159 END > 160 */ > 161 } > 162 // END CUT HERE