fork download
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3.  
  4. int main() {
  5. using namespace std;
  6. using namespace chrono;
  7. using namespace __gnu_pbds;
  8. using clock = high_resolution_clock;
  9. const int M = 2, N = 2e4;
  10. using ivec = array<int,N>;
  11. using imat = array<ivec,M>;
  12. using iset = set<int>;
  13. mt19937 random(clock::now().time_since_epoch().count());
  14. set<int> s;
  15. tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> t;
  16. const function<int(int)> tester[] = {
  17. [&](int x){ return int(distance(s.begin(),s.find(x))); },
  18. [&](int x){ return int(t.order_of_key(x)); } };
  19. int v[N], result[M][N];
  20. const auto test_set = [&](const string& prompt, int i) {
  21. const auto t0 = clock::now();
  22. const auto& f = tester[i];
  23. for (int j = 0; j < N; ++j)
  24. result[i][j] = f(v[j]);
  25. const auto t1 = clock::now();
  26. const auto time = duration_cast<milliseconds>(t1-t0).count();
  27. cout << prompt << ": elapsed time = " << time << " msec." << endl; };
  28. for (int x, size = 0; size < N; )
  29. if (x = random(), s.find(x) == s.end())
  30. s.insert(x), t.insert(x), v[size++] = x;
  31. shuffle(v,v+N,random), test_set("iset",0), test_set("oset",1);
  32. for (int j = 0; j < N; ++j)
  33. if (result[0][j] != result[1][j])
  34. cout << "Failed.", exit(0);
  35. cout << "Passed"; }
  36.  
Success #stdin #stdout 2.84s 5700KB
stdin
Standard input is empty
stdout
iset: elapsed time = 2834 msec.
oset: elapsed time = 2 msec.
Passed