• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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, B);}) == A.size();
           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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           72  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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,79,83,89,97};
          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,79,83,89,97};
          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[v]-y[u]);
           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, double sx2)
           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) << " msec)"; return os.str(); }
          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 os; }
          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() << endl;
          114  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          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, -766795, -664177, 267757, -291856, -765547, 604801, -682922, -404590, 468001, 607925, 503849, -499699, -798637};
          149  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          150  + int y_[] = {-12396, -66098, -56843, 20270, 81510, -23294, 10423, 24007, -24343, -21587, -6318, -7396, -68622, 56304, -85680, -14890, -38373, -25477, -38240, 11736};
          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, -119436, -620920, -470018, -914272, -691256, -49418, -21054, 603373, -23656, 891691, 258986, -453793, -782940};
          156  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          157  + int y_[] = {-77318, -632629, -344942, -361706, 191982, 349424, 676536, 166124, 291342, -268968, 188262, -537953, -70432, 156803, 166174, 345128, 58614, -671747, 508265, 92324};
          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