Advertisement
daniliambo

Untitled

Nov 21st, 2023
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <deque>
  5. #include <random>
  6. #include <stdexcept>
  7. #include <fstream>
  8. #include <sstream>
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <numeric>
  12.  
  13. using std::cin;
  14. using std::cout;
  15. using std::endl;
  16. using std::ofstream;
  17. using std::vector;
  18.  
  19. inline int64_t Modulo(int64_t ii, int64_t nn)
  20. {
  21. return ((ii % nn) + nn) % nn;
  22. };
  23.  
  24. struct Triangle
  25. {
  26. Triangle(int64_t aa, int64_t bb, int64_t cc, int64_t size) : aa_(aa), bb_(bb), cc_(cc), size_(size)
  27. {
  28. vector<int64_t> vals = {aa, bb, cc};
  29. int64_t gcd = std::gcd(std::gcd(aa, bb), cc);
  30. std::sort(vals.begin(), vals.end());
  31. aa_ = vals[0] / gcd;
  32. bb_ = vals[1] / gcd;
  33. cc_ = vals[2] / gcd;
  34. hash_ = CalculatePolyHash_();
  35. };
  36.  
  37. bool operator*(Triangle &other)
  38. {
  39. return ((aa_ == other.aa_) && (bb_ == other.bb_) && (cc_ == other.cc_));
  40. };
  41. int64_t hash_;
  42.  
  43. private:
  44. // std::size_t CalculatePolyHash_()
  45. // {
  46. // std::size_t first = std::hash<unsigned long long>{}(aa_);
  47. // std::size_t second = std::hash<unsigned long long>{}(bb_);
  48. // std::size_t third = std::hash<unsigned long long>{}(cc_);
  49. // return first ^ (second << 1) ^ (third << 3);
  50. // };
  51.  
  52. int64_t CalculatePolyHash_()
  53. {
  54. vector<int64_t> vector = {aa_, bb_, cc_};
  55. int64_t pp = std::pow(10, 9) + 7;
  56. int64_t length = 3;
  57.  
  58. int64_t hash = 0;
  59. for (int64_t i = 0; i < length; ++i)
  60. {
  61. int64_t el = vector[i];
  62. int64_t val = std::pow(el * pp, length - (i + 1));
  63. hash += val;
  64. }
  65. return Modulo(hash, size_);
  66. };
  67. int64_t size_;
  68. int64_t aa_;
  69. int64_t bb_;
  70. int64_t cc_;
  71. };
  72.  
  73. class FixedSet
  74. {
  75. public:
  76. FixedSet() = default;
  77. void InsertTriangle(Triangle &triangle);
  78. int64_t GetHashMapSize();
  79. void InitVector();
  80. int64_t size_ = 1'000'000 / 1000;
  81.  
  82. private:
  83. vector<vector<Triangle>> hash_map_{};
  84. int64_t hashMapSize_ = 0;
  85. };
  86.  
  87. int64_t FixedSet::GetHashMapSize()
  88. {
  89. return hashMapSize_;
  90. };
  91.  
  92. void FixedSet::InitVector()
  93. {
  94. for (int i = 0; i < size_; ++i)
  95. {
  96. hash_map_.push_back({});
  97. }
  98. }
  99.  
  100. //
  101.  
  102. void FixedSet::InsertTriangle(Triangle &triangle)
  103. {
  104. int idx = triangle.hash_;
  105.  
  106. for (Triangle cur_trinagle : hash_map_[idx])
  107. {
  108. if (cur_trinagle * triangle)
  109. {
  110. return;
  111. }
  112. }
  113. hash_map_[idx].push_back(triangle);
  114. ++hashMapSize_;
  115. };
  116.  
  117. int main()
  118. {
  119. int64_t nn;
  120. cin >> nn;
  121. FixedSet fixedSet;
  122. fixedSet.InitVector();
  123.  
  124. while (nn--)
  125. {
  126. int64_t aa, bb, cc;
  127. cin >> aa;
  128. cin >> bb;
  129. cin >> cc;
  130. Triangle tri(aa, bb, cc, fixedSet.size_);
  131. fixedSet.InsertTriangle(tri);
  132. }
  133.  
  134. cout << fixedSet.GetHashMapSize() << endl;
  135.  
  136. return 0;
  137. }
  138.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement