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

Added SRM/733-U/1A.cpp version [81754a22440fcdd8]

            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 Rat {
           23  + LL s, b;  // s/b
           24  +
           25  + Rat(LL s, LL b) : s(s), b(b) {}
           26  +
           27  + // take abs() too
           28  + Rat operator-(const Rat& rhs) {
           29  +  LL a = s, c = rhs.s, d = rhs.b;
           30  +  return Rat(abs(a*d - b*c), b*d);
           31  + }
           32  +
           33  + bool operator<(const Rat& rhs) {
           34  +  unsigned long long a = s, c = rhs.s, d = rhs.b;
           35  +  return a*d < b*c;
           36  + }
           37  +};
           38  +
           39  +class MinimizeAbsoluteDifferenceDiv1 { public:
           40  + vector <int> findTuple(vector <int> x)
           41  + {
           42  +  vector<int> idx = { 0,1,2,3,4 };
           43  +  vector<int> best;
           44  +  Rat bestval(0, 0);
           45  +  do {
           46  +   Rat val = Rat(x[idx[0]], x[idx[1]]) - Rat(x[idx[2]], x[idx[3]]);
           47  +   if (best.empty() || val < bestval)
           48  +    best = idx, bestval = val;
           49  +  } while (next_permutation(idx.begin(), idx.end()));
           50  +
           51  +  best.resize(4);
           52  +  return best;
           53  + }
           54  +};
           55  +
           56  +// BEGIN CUT HERE
           57  +#include <ctime>
           58  +double start_time; string timer()
           59  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           60  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           61  + { os << "{ ";
           62  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           63  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           64  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           65  + bool ok = (Expected == Received);
           66  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           67  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           68  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           69  +#define END  verify_case(_, MinimizeAbsoluteDifferenceDiv1().findTuple(x));}
           70  +int main(){
           71  +
           72  +CASE(0)
           73  + int x_[] = {1,1,1,1,1};
           74  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           75  + int __[] = {0, 1, 2, 3 };
           76  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           77  +END
           78  +CASE(1)
           79  + int x_[] = {2,3,5,7,11};
           80  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           81  + int __[] = {0, 3, 1, 4 };
           82  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           83  +END
           84  +CASE(2)
           85  + int x_[] = {8, 2, 4, 2, 6};
           86  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           87  + int __[] = {1, 0, 3, 4 };
           88  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           89  +END
           90  +CASE(3)
           91  + int x_[] = {124, 182, 9, 33, 70};
           92  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           93  + int __[] = {2, 4, 3, 1 };
           94  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           95  +END
           96  +CASE(4)
           97  + int x_[] = {9947, 3, 7, 11, 13};
           98  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           99  + int __[] = {1, 4, 3, 0 };
          100  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          101  +END
          102  +CASE(5)
          103  + int x_[] = {10000, 4, 10, 4, 10};
          104  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          105  + int __[] = {1, 2, 3, 4 };
          106  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          107  +END
          108  +/*
          109  +CASE(6)
          110  + int x_[] = ;
          111  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          112  + int __[] = ;
          113  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          114  +END
          115  +CASE(7)
          116  + int x_[] = ;
          117  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          118  + int __[] = ;
          119  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          120  +END
          121  +*/
          122  +}
          123  +// END CUT HERE

Added SRM/733-U/1B.cpp version [39d81aae764f5374]

            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  + {
           29  +  for (int i = 0; i<N; ++i) uf[i] = i;
           30  + }
           31  + int size()
           32  + {
           33  +  return nc;
           34  + }
           35  + int size(int a)
           36  + {
           37  +  return sz[Find(a)];
           38  + }
           39  + int Find(int a)
           40  + {
           41  +  return uf[a] == a ? a : uf[a] = Find(uf[a]);
           42  + }
           43  + // Semi-compression w.o. recursion.
           44  + //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; }
           45  + bool Union(int a, int b)
           46  + {
           47  +  a = Find(a);
           48  +  b = Find(b);
           49  +  if (a != b)
           50  +  {
           51  +   if (sz[a] >= sz[b]) swap(a, b);
           52  +   uf[a] = b;
           53  +   sz[b] += sz[a];
           54  +   --nc;
           55  +  }
           56  +  return (a != b);
           57  + }
           58  +};
           59  +
           60  +static const unsigned MODVAL = 987654323;
           61  +struct mint
           62  +{
           63  + unsigned val;
           64  + mint() :val(0) {}
           65  + mint(int      x) :val((x+MODVAL)%MODVAL) {}
           66  + mint(unsigned x) :val(x%MODVAL) {}
           67  + mint(LL       x) :val((x+MODVAL)%MODVAL) {}
           68  +};
           69  +mint& operator+=(mint& x, mint y) { return x = x.val + y.val; }
           70  +mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; }
           71  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           72  +mint operator+(mint x, mint y) { return x += y; }
           73  +mint operator-(mint x, mint y) { return x -= y; }
           74  +mint operator*(mint x, mint y) { return x *= y; }
           75  +
           76  +mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= x; return v; }
           77  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); }
           78  +mint operator/(mint x, mint y) { return x /= y; }
           79  +
           80  +mint det(vector<vector<mint>> M)
           81  +{
           82  + const int n = M.size();
           83  + mint ans = 1;
           84  +
           85  + for (int i=0; i<n; ++i)
           86  + {
           87  +  // pivot
           88  +  if (M[i][i].val == 0)
           89  +   for (int j = i + 1; j<n; ++j)
           90  +    if (M[j][i].val != 0)
           91  +    {
           92  +     swap(M[i], M[j]);
           93  +     break;
           94  +    }
           95  +  if (M[i][i].val == 0)
           96  +   return 0;
           97  +
           98  +  ans *= M[i][i];
           99  +
          100  +  // M[i][i] <-- 1
          101  +  mint rp = POW(M[i][i], MODVAL-2);
          102  +  for (int j = i; j<n; ++j)
          103  +   M[i][j] *= rp;
          104  +
          105  +  // M[*][i] <-- 0
          106  +  for (int j = i+1; j<n; ++j)
          107  +  {
          108  +   mint r = M[j][i];
          109  +   for (int k = i + 1; k < n; ++k)
          110  +    M[j][k] -= M[i][k] * r;
          111  +  }
          112  + }
          113  + return ans;
          114  +}
          115  +
          116  +class BuildingSpanningTreesDiv1 { public:
          117  + int getNumberOfSpanningTrees(int n, vector <int> x, vector <int> y)
          118  + {
          119  +  for (auto& xi : x) --xi;
          120  +  for (auto& yi : y) --yi;
          121  +
          122  +  UnionFind uf(n);
          123  +  for (int i = 0; i < x.size(); ++i)
          124  +   if (!uf.Union(x[i], y[i]))
          125  +    return 0;
          126  +
          127  +  vector<int> w;
          128  +  for (int v = 0; v < n; ++v)
          129  +   if (uf.Find(v) == v)
          130  +    w.push_back(uf.size(v));
          131  +
          132  +  // complete graph with |w| vertices, w[i]--w[j] has w[i]*w[j] multiple edges.
          133  +
          134  +  const int N = w.size();
          135  +  vector<vector<mint>> lap(N-1, vector<mint>(N-1));
          136  +  for (int v = 0; v < N - 1; ++v)
          137  +   for (int u = 0; u < N - 1; ++u)
          138  +    lap[v][u] = (v == u ? w[v] * (n - w[v]) : - w[v] * w[u]);
          139  +  return det(lap).val;
          140  + }
          141  +};
          142  +
          143  +// BEGIN CUT HERE
          144  +#include <ctime>
          145  +double start_time; string timer()
          146  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          147  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          148  + { os << "{ ";
          149  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          150  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          151  +void verify_case(const int& Expected, const int& Received) {
          152  + bool ok = (Expected == Received);
          153  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          154  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          155  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          156  +#define END  verify_case(_, BuildingSpanningTreesDiv1().getNumberOfSpanningTrees(n, x, y));}
          157  +int main(){
          158  +
          159  +CASE(0)
          160  + int n = 3;
          161  + int x_[] = {1,2};
          162  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          163  + int y_[] = {2,3};
          164  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          165  + int _ = 1;
          166  +END
          167  +CASE(1)
          168  + int n = 5;
          169  + int x_[] = {1,3,4};
          170  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          171  + int y_[] = {2,4,5};
          172  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          173  + int _ = 6;
          174  +END
          175  +CASE(2)
          176  + int n = 4;
          177  + int x_[] = {1};
          178  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          179  + int y_[] = {2};
          180  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          181  + int _ = 8;
          182  +END
          183  +CASE(3)
          184  + int n = 4;
          185  + int x_[] = {1,2,1};
          186  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          187  + int y_[] = {2,3,3};
          188  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          189  + int _ = 0;
          190  +END
          191  +CASE(4)
          192  + int n = 8;
          193  + int x_[] = {1,4,2,3,5};
          194  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          195  + int y_[] = {4,7,6,5,8};
          196  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          197  + int _ = 144;
          198  +END
          199  +CASE(5)
          200  + int n = 1000;
          201  + int x_[] = {1};
          202  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          203  + int y_[] = {2};
          204  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          205  + int _ = 529013784;
          206  +END
          207  +/*
          208  +CASE(6)
          209  + int n = ;
          210  + int x_[] = ;
          211  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          212  + int y_[] = ;
          213  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          214  + int _ = ;
          215  +END
          216  +CASE(7)
          217  + int n = ;
          218  + int x_[] = ;
          219  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          220  + int y_[] = ;
          221  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          222  + int _ = ;
          223  +END
          224  +*/
          225  +}
          226  +// END CUT HERE