Overview
| SHA1 Hash: | 3c4124479ff39a2266724a6e286e6232ab214c39 |
|---|---|
| Date: | 2014-04-04 10:32:13 |
| User: | kinaba |
| Comment: | 611 |
| 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/611-U/1A.cpp version [9f21bd311202df25]
> 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 LL gcd(LL a, LL b) > 23 { > 24 while(a) > 25 swap(a, b%=a); > 26 return b; > 27 } > 28 > 29 LL lcm(LL a, LL b) > 30 { > 31 return a/gcd(a,b)*b; > 32 } > 33 > 34 class LCMSet { public: > 35 string equal(vector <int> A, vector <int> B) > 36 { > 37 return is_equal(A,B) ? "Equal" : "Not equal"; > 38 } > 39 > 40 bool is_equal(const vector<int>& A, const vector<int>& B) > 41 { > 42 return can_make(A, B) && can_make(B, A); > 43 } > 44 > 45 bool can_make(const vector<int>& A, const vector<int>& B) > 46 { > 47 return count_if(A.begin(), A.end(), [&](int a){return can_make(a > 48 } > 49 > 50 bool can_make(int a, const vector<int>& B) > 51 { > 52 LL cur = 1; > 53 for(int b: B) { > 54 if(lcm(lcm(cur, b), a) == a) > 55 cur = lcm(cur, b); > 56 } > 57 return a == cur; > 58 } > 59 }; > 60 > 61 // BEGIN CUT HERE > 62 #include <ctime> > 63 double start_time; string timer() > 64 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 65 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 66 { os << "{ "; > 67 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 68 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 69 void verify_case(const string& Expected, const string& Received) { > 70 bool ok = (Expected == Received); > 71 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 73 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 74 #define END verify_case(_, LCMSet().equal(A, B));} > 75 int main(){ > 76 > 77 CASE(0) > 78 int A_[] = {2,3,4,12}; > 79 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 80 int B_[] = {2,3,4,6}; > 81 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 82 string _ = "Equal"; > 83 END > 84 CASE(1) > 85 int A_[] = {4,9}; > 86 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 87 int B_[] = {6,36}; > 88 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 89 string _ = "Not equal"; > 90 END > 91 CASE(2) > 92 int A_[] = {2,3,5,7,14,105}; > 93 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 94 int B_[] = {2,3,5,6,7,30,35}; > 95 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 96 string _ = "Equal"; > 97 END > 98 CASE(3) > 99 int A_[] = {2,3,5,7,14,105}; > 100 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 101 int B_[] = {2,3,5,6,7,30,36}; > 102 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 103 string _ = "Not equal"; > 104 END > 105 CASE(4) > 106 int A_[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,7 > 107 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 108 int B_[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,7 > 109 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 110 string _ = "Equal"; > 111 END > 112 CASE(5) > 113 int A_[] = {999999999,1953125,512,1000000000}; > 114 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 115 int B_[] = {999999999,1953125,512}; > 116 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 117 string _ = "Equal"; > 118 END > 119 CASE(6) > 120 int A_[] = {999999998,999999999,1000000000}; > 121 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 122 int B_[] = {999999999,1000000000}; > 123 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 124 string _ = "Not equal"; > 125 END > 126 /* > 127 CASE(7) > 128 int A_[] = ; > 129 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 130 int B_[] = ; > 131 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 132 string _ = ; > 133 END > 134 CASE(8) > 135 int A_[] = ; > 136 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 137 int B_[] = ; > 138 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 139 string _ = ; > 140 END > 141 */ > 142 } > 143 // END CUT HERE
Added SRM/611-U/1B-U.cpp version [4fdd1dfbd4a03197]
> 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 Egalitarianism2 { public: > 51 int N; > 52 vector<vector<LL>> d2table; > 53 > 54 typedef tuple<LL, int, int> edge; > 55 > 56 double minStdev(vector <int> x, vector <int> y) > 57 { > 58 N = x.size(); > 59 d2table.resize(N, vector<LL>(N)); > 60 for(int v=0; v<N; ++v) > 61 for(int u=0; u<N; ++u) > 62 d2table[v][u] = (x[v]-x[u])*(x[v]-x[u]) + (y[v]-y[u])*(y > 63 > 64 vector<edge> edges; > 65 for(int v=0; v<N; ++v) > 66 for(int u=v+1; u<N; ++u) > 67 edges.emplace_back(d2table[v][u], v, u); > 68 sort(edges.begin(), edges.end()); > 69 > 70 UnionFind uf(N); > 71 return sqrt(rec(0, uf, edges, 0, 0)); > 72 } > 73 > 74 double rec(int i, UnionFind& uf, const vector<edge>& edges, double sx, d > 75 { > 76 if(uf.size() == 1) > 77 return sx2/(N-1) - sx*sx/(N-1)/(N-1); > 78 if(i==edges.size()) > 79 return 1e+300; > 80 > 81 vector<int> cand; > 82 int e=i; > 83 for(; e<edges.size() && get<0>(edges[i])==get<0>(edges[e]); ++e) > 84 if(uf.Find(get<1>(edges[e])) != uf.Find(get<2>(edges[e]) > 85 cand.push_back(e); > 86 > 87 if(cand.empty()) > 88 return rec(e, uf, edges, sx, sx2); > 89 > 90 double best = 1e+300; > 91 for(int e: cand) { > 92 UnionFind uf2 = uf; > 93 LL d = get<0>(edges[e]); > 94 int u = get<1>(edges[e]); > 95 int v = get<2>(edges[e]); > 96 uf2.Union(u, v); > 97 best = min(best, rec(e+1, uf2, edges, sx+sqrt(d), sx2+d) > 98 } > 99 return best; > 100 } > 101 }; > 102 > 103 // BEGIN CUT HERE > 104 #include <ctime> > 105 double start_time; string timer() > 106 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 107 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 108 { os << "{ "; > 109 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 110 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 111 void verify_case(const double& Expected, const double& Received) { > 112 bool ok = (abs(Expected - Received) < 1e-9); > 113 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 114 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 115 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 116 #define END verify_case(_, Egalitarianism2().minStdev(x, y));} > 117 int main(){ > 118 > 119 CASE(0) > 120 int x_[] = {0,0,1,1}; > 121 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 122 int y_[] = {0,1,0,1}; > 123 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 124 double _ = 0.0; > 125 END > 126 CASE(1) > 127 int x_[] = {0,0,0}; > 128 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 129 int y_[] = {0,9,10}; > 130 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 131 double _ = 0.5; > 132 END > 133 CASE(2) > 134 int x_[] = {12,46,81,56}; > 135 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 136 int y_[] = {0,45,2,67}; > 137 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 138 double _ = 6.102799971320872; > 139 END > 140 CASE(3) > 141 int x_[] = {0,0,0,0,0,0,0}; > 142 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 143 int y_[] = {0,2,3,9,10,15,16}; > 144 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 145 double _ = 0.9428090415820617; > 146 END > 147 CASE(4) > 148 int x_[] = {167053, 536770, -590401, 507047, 350178, -274523, -584679, - > 149 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 150 int y_[] = {-12396, -66098, -56843, 20270, 81510, -23294, 10423, 24007, > 151 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 152 double _ = 40056.95946451678; > 153 END > 154 CASE(5) > 155 int x_[] = {-306880, 169480, -558404, -193925, 654444, -300247, -456420, > 156 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 157 int y_[] = {-77318, -632629, -344942, -361706, 191982, 349424, 676536, 1 > 158 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 159 double _ = 36879.1512763429; > 160 END > 161 /* > 162 CASE(6) > 163 int x_[] = ; > 164 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 165 int y_[] = ; > 166 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 167 double _ = ; > 168 END > 169 CASE(7) > 170 int x_[] = ; > 171 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 172 int y_[] = ; > 173 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 174 double _ = ; > 175 END > 176 */ > 177 } > 178 // END CUT HERE