fork(15) download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int MAXN = 1048576;
  6. long long solve(vector<int> &contain)
  7. {
  8. 	if(contain.size()==1)
  9. 		return 1LL*contain[0]*contain[0];
  10.  
  11. 	vector<int> halved(contain.size()/2);
  12. 	for(int i=0;i<contain.size()/2;i++)
  13. 		halved[i]=contain[i+contain.size()/2];
  14. 	long long ans = -solve(halved);
  15.  
  16. 	for(int i=0;i<contain.size()/2;i++)
  17. 		halved[i]+=contain[i];
  18. 	ans+=solve(halved);
  19.  
  20. 	return ans;
  21. }
  22. void tmain()
  23. {
  24. 	int N;
  25. 	vector<int> contain(MAXN);
  26. 	scanf("%d",&N);
  27. 	for(int i=0;i<N;i++)
  28. 	{
  29. 		int t;
  30. 		scanf("%d",&t);
  31. 		contain[t]++;
  32. 	}
  33. 	printf("%lld\n",solve(contain));
  34. }
  35. int main()
  36. {
  37. 	int T;
  38. 	scanf("%d",&T);
  39. 	while(T--)
  40. 		tmain();
  41. 	return 0;
  42. }
Success #stdin #stdout 0.3s 3416KB
comments (?)
stdin
copy 
2
5
41 47 34 40 29
3
3 6 0
stdout
copy 
2
5
https://ideone.com/UzPzMh
language:
C++14 (gcc 8.3)
created:
9 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!