fork(3) download 
  1. #pragma comment(linker, "/stack:20000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. # include <iostream>
  4. # include <cmath>
  5. # include <algorithm>
  6. # include <stdio.h>
  7. # include <cstring>
  8. # include <string>
  9. # include <cstdlib>
  10. # include <vector>
  11. # include <bitset>
  12. # include <map>
  13. # include <queue>
  14. # include <ctime>
  15. # include <stack>
  16. # include <set>
  17. # include <list>
  18. # include <random>
  19. # include <deque>
  20. # include <functional>
  21. # include <iomanip>
  22. # include <sstream>
  23. # include <fstream>
  24. # include <complex>
  25. # include <numeric>
  26. # include <immintrin.h>
  27. # include <cassert>
  28.  
  29. using namespace std;
  30.  
  31. // Let's define unordered map
  32. # ifdef __GNUC__
  33. # if __cplusplus > 199711L
  34. # include <unordered_set>
  35. # include <unordered_map>
  36. # else
  37. # include <tr1/unordered_map>
  38. # include <tr1/unordered_set>
  39. using namespace tr1;
  40. # endif
  41. # else
  42. # include <unordered_map>
  43. # include <unordered_set>
  44. # endif
  45.  
  46. #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
  47. #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  48. #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
  49. #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  50. #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  51. #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  52. #define macro_dispatcher___(macro, nargs) macro ## nargs
  53. #define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
  54. #define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  55. #define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  56. #define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  57. #define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  58. #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
  59. #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  60. #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
  61. #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
  62.  
  63. #ifdef _MSC_VER
  64. #define ALIGN(x) __declspec(align(x))
  65. #else
  66. #define ALIGN(x) __attribute__((aligned(x)))
  67. #endif
  68.  
  69. #ifdef LOCAL
  70. #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
  71. #else
  72. #define CURTIME() ;
  73. #endif
  74. double __begin;
  75. #define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
  76.  
  77. #define mp make_pair
  78. typedef long long ll;
  79. typedef unsigned int uint;
  80. typedef unsigned long long ull;
  81. typedef pair<int, int> pii;
  82. typedef pair<long long, long long> pll;
  83. typedef vector<int> vi;
  84. typedef vector<long long> vll;
  85. typedef int itn;
  86.  
  87. template<class T1, class T2, class T3>
  88. struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  89. template<class T1, class T2, class T3>
  90. bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
  91. template<class T1, class T2, class T3>
  92. bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
  93. #define tri triple<int,int,int>
  94. #define trll triple<ll,ll,ll>
  95.  
  96. #define FI(n) for(int i=0;i<n;++i)
  97. #define FJ(n) for(int j=0;j<n;++j)
  98. #define FK(n) for(int k=0;k<n;++k)
  99. #define FL(n) for(int l=0;l<n;++l)
  100. #define FQ(n) for(int q=0;q<n;++q)
  101. #define all(a) std::begin(a), std::end(a)
  102. #define reunique(v) v.resize(unique(v.begin(), v.end()) - v.begin())
  103.  
  104. #define sqr(x) ((x) * (x))
  105. #define sqrt(x) sqrt(1.0 * (x))
  106. #define pow(x, n) pow(1.0 * (x), n)
  107.  
  108. #define COMPARE(obj) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b)
  109. #define COMPARE_BY(obj, field) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b) { return a.field < b.field; }
  110.  
  111. #define checkbit(n, b) (((n) >> (b)) & 1)
  112. #define setbit(n, b) ((n) | (static_cast<decltype(n)>(1) << (b)))
  113. #define removebit(n, b) (~setbit(~(n), (b)))
  114. inline int bits_count(int v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
  115. inline int bits_count(ll v){int t=v>>32;int p=(v& ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
  116. unsigned int reverse_bits(register unsigned int x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  117. template<class T>
  118. inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
  119. inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  120.  
  121. //STL output *****************************************************************************************************
  122. #define TT1 template<class T>
  123. #define TT1T2 template<class T1, class T2>
  124. #define TT1T2T3 template<class T1, class T2, class T3>
  125. TT1T2 inline ostream& operator << (ostream& os, const pair<T1, T2>& p);
  126. TT1 inline ostream& operator << (ostream& os, const vector<T>& v);
  127. TT1T2 inline ostream& operator << (ostream& os, const set<T1, T2>&v);
  128. TT1T2 inline ostream& operator << (ostream& os, const multiset<T1, T2>&v);
  129. TT1T2 inline ostream& operator << (ostream& os, priority_queue<T1, T2> v);
  130. TT1T2T3 inline ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
  131. TT1T2T3 inline ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
  132. TT1T2T3 inline ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
  133. TT1T2 inline ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
  134. TT1 inline ostream& operator << (ostream& os, const vector<T>& v){ bool fi = 1; os << "["; for (int i = 0; i<v.size(); i++){ if (!fi)os << ", "; os << v[i]; fi = 0; }return os << "]"; }
  135. TT1T2 inline ostream& operator << (ostream& os, const set<T1, T2>&v){ bool fi = 1; os << "["; for (auto ii = v.begin(); ii != v.end(); ++ii){ if (!fi)os << ", "; os << *ii; fi = 0; }return os << "]"; }
  136. TT1T2 inline ostream& operator << (ostream& os, const multiset<T1, T2>&v){ bool fi = 1; os << "["; for (auto ii = v.begin(); ii != v.end(); ++ii){ if (!fi)os << ", "; os << *ii; fi = 0; }return os << "]"; }
  137. TT1T2T3 inline ostream& operator << (ostream& os, const map<T1, T2, T3>& v){ bool fi = 1; os << "["; for (auto ii = v.begin(); ii != v.end(); ++ii){ if (!fi)os << ", "; os << "(" << ii->first << " -> " << ii->second << ") "; fi = 0; }return os << "]"; }
  138. TT1T2 inline ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool fi = 1; os << "["; for (auto ii = v.begin(); ii != v.end(); ++ii){ if (!fi)os << ", "; os << "(" << ii->first << " -> " << ii->second << ") "; fi = 0; }return os << "]"; }
  139. TT1T2 inline ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool fi = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!fi) os << ", "; fi = 0; os << x; } return os << "]"; }
  140. TT1T2T3 inline ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  141. TT1T2 void printarray(T1 a[], T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  142.  
  143. //STL input *****************************************************************************************************
  144. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
  145. TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
  146. TT1 inline istream& operator >> (istream& os, vector<T>& v) {
  147.     if (v.size()) for (T& t : v) os >> t; else {
  148.         string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
  149.         stringstream ss(s); while (ss >> obj) v.push_back(obj);
  150.     }
  151.     return os;
  152. }
  153. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
  154.  
  155. //Pair magic *****************************************************************************************************
  156. #define PT1T2 pair<T1, T2>
  157. TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
  158. TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
  159.  
  160. #undef TT1
  161. #undef TT1T2
  162. #undef TT1T2T3
  163.  
  164. #define FREIN(FILE) freopen(FILE, "rt", stdin)
  165. #define FREOUT(FILE) freopen(FILE, "wt", stdout)
  166.  
  167. template<class T> bool isPrime(T x) { if (x < 2) return 0; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return 0; return 1; }
  168. inline void normmod(ll &x, ll m) { x %= m; if (x < 0) x += m; }
  169. inline ll summodfast(ll x, ll y, ll m) { ll res = x + y; if (res >= m) res -= m; return res; }
  170. inline int summodfast(int x, int y, int m) { int res = x + y; if (res >= m) res -= m; return res; }
  171. inline void addmodfast(ll &x, ll y, ll m) { x += y; if (x >= m) x -= m; }
  172. inline void addmodfast(int &x, int y, int m) { x += y; if (x >= m) x -= m; }
  173. inline void submodfast(ll &x, ll y, ll m) { x -= y; if (x < 0) x += m; }
  174. inline void submodfast(int &x, int y, int m) { x -= y; if (x < 0) x += m; }
  175. inline ll mulmod(ll x, ll n, ll m){ ll res = 0; normmod(x, m); normmod(n, m); while (n){ if (n & 1) res = summodfast(res, x, m); x = summodfast(x, x, m); n >>= 1; } return res; }
  176. inline ll powmod(ll x, ll n, ll m){ ll res = 1; while (n){ if (n & 1)res = (res*x) % m; x = (x*x) % m; n >>= 1; }return res; }
  177. inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
  178. inline int gcd(int a, int b){ int t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
  179. inline ll lcm(ll a, ll b){ return a / gcd(a, b)*b; }
  180. inline ll gcd(ll a, ll b, ll c){ return gcd(gcd(a, b), c); }
  181. inline int gcd(int a, int b, int c){ return gcd(gcd(a, b), c); }
  182. ll gcdex(ll a, ll b, ll& x, ll& y) {
  183.     if (!a) { x = 0; y = 1; return b; }
  184.     ll y1;
  185.     ll d = gcdex(b % a, a, y, y1);
  186.     x = y1 - (b / a) * y;
  187.     return d;
  188. }
  189.  
  190. // Useful constants
  191.  
  192. //int some_primes[10] = {24443, 100271, 500179, 1000003, 1000333, 2000321, 5000321, 98765431, 1000000123};
  193. #define INF         1011111111
  194. #define LLINF       1000111000111000111LL
  195. #define EPS         (double)1e-10
  196. #define mod         1000000007
  197. #define PI          3.14159265358979323
  198. #define link        asaxlajrewqwe
  199. #define rank        wahayawehasdakw
  200. //*************************************************************************************
  201.  
  202. const int maxn = 10000000;
  203. int p[maxn + 1000];
  204. int getp_calls = 0;
  205. int getp(int x) {
  206.     ++getp_calls;
  207.     if (p[x] != x) {
  208.         p[x] = getp(p[x]);
  209.     }
  210.     return p[x];
  211. }
  212. std::mt19937 gen(123);
  213.  
  214. void join( int a, int b ) {
  215.     int pa = getp(a);
  216.     int pb = getp(b);
  217.     if (pa == pb) {
  218.         return;
  219.     }
  220.     if (uniform_int_distribution<>(0, 1)(gen)) {
  221.         p[pa] = p[a] = pb;
  222.     } else {
  223.         p[pb] = p[b] = pa;
  224.     }
  225. }
  226.  
  227. double solve(int n) {
  228.     getp_calls = 0;
  229.     for (int i = 1; i <= n; ++i) {
  230.         p[i] = i;
  231.     }
  232.     int k = n / log(n);
  233.     for (int i = 2; i <= n; ++i) {
  234.         join(uniform_int_distribution<>(1, k)(gen), i);
  235.     }
  236.     return getp_calls * 1.0 / n;
  237. }
  238.  
  239. int main() {
  240.     for (int n : {1e2, 1e3, 1e4, 1e5, 1e6, 1e7}) {
  241.         DBN(n, solve(n));
  242.     }
  243.     return 0;
  244. }
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
Success #stdin #stdout #stderr 3.73s 55120KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
n=100, solve(n)=4.77
n=1000, solve(n)=5.764
n=10000, solve(n)=7.036
n=100000, solve(n)=8.53946
n=1000000, solve(n)=9.96357
n=10000000, solve(n)=11.664
https://ideone.com/iUu2S3
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!