Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <random>
  5.  
  6. using namespace std;
  7.  
  8. const int SIZE = 251;
  9. const int FUNC = 50;
  10.  
  11. int64_t table[FUNC][SIZE];
  12. vector<pair<int, int>> seed;
  13.  
  14. int get_hash(int id, int64_t a, int64_t b) {
  15.     return (a + b * id) % SIZE;
  16. }
  17.  
  18. int main() {
  19.     int n;
  20.     cin >> n;
  21.  
  22.     std::random_device rd;
  23.     std::mt19937 gen(rd());
  24.     std::uniform_int_distribution<int> dist(100000, numeric_limits<int>::max());
  25.  
  26.     for (int i = 0; i < n; ++i) {
  27.         int id, pay;
  28.         cin >> id >> pay;
  29.  
  30.         for (int j = 0; j < FUNC; ++j) {
  31.             int a = dist(gen);
  32.             int b = dist(gen);
  33.             seed.push_back({a, b});
  34.             table[j][get_hash(id, a, b)] += pay;
  35.         }
  36.     }
  37.  
  38.     int card;
  39.     cin >> card;
  40.     int64_t ans = numeric_limits<int64_t>::max();
  41.  
  42.     for (int i = 0; i < FUNC; ++i) {
  43.        
  44.         int a = seed[i].first;
  45.         int b = seed[i].second;
  46.         int hash = get_hash(card, a, b);
  47.  
  48.         for (int j = 0; j < SIZE; ++j) {
  49.             ans = min(ans, table[i][hash]);
  50.         }
  51.     }
  52.     cout << ans << '\n';
  53.  
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement