fork download 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <array>
  6.  
  7. using namespace std;
  8.  
  9. constexpr int limit = 10000;
  10. constexpr int diff = 32;
  11. constexpr int bucket_num = (limit/diff)+1;
  12.  
  13. int adjacent_buckets(const vector<int>& bucket1, const vector<int>& bucket2)
  14. {
  15.     std::array<int,diff> pairs{};
  16.     for(int number : bucket1)
  17.      {
  18.          for(int i=0;i<number;i++)
  19.             pairs[i]++;
  20.      }
  21.  
  22.     return std::accumulate(bucket2.begin(), bucket2.end(), 0,
  23.                            [&pairs](int s, int n){ return s + pairs[n]; }); 
  24. }
  25.  
  26. void solve()
  27. {
  28. 	int i,n;
  29. 	std::array<std::vector<int>,bucket_num> buckets;
  30.  
  31. 	cin>>n;
  32. 	int number;
  33. 	for(i=0;i<n;i++)
  34. 	{
  35. 	    cin >> number;
  36. 	    buckets[number/diff].push_back(number%diff);
  37. 	}
  38.  
  39. 	int result = std::accumulate(buckets.begin(), buckets.end(), 0,
  40.                   [](int s, vector<int>& v){ return s + (v.size()*(v.size()-1))/2; }); 
  41.  
  42.     for(int i=0;i<bucket_num-1;i++)
  43.    		if(buckets[i].size() && buckets[i+1].size())
  44.     		result += adjacent_buckets(buckets[i], buckets[i+1]);
  45.  
  46.     cout << result << endl;
  47. }
  48.  
  49. int main() {
  50. 	int T;
  51.     cin >> T;
  52.     for (int i=0 ; i<T ; i++)
  53.         solve();
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 16064KB
comments ()
stdin 
2
4
1 16 32 64
5
1 100 110 100 1
stdout 
3
4
https://ideone.com/rUHgxL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!