fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27. // 2
  28. // 7
  29. // 1 2 3 4 -1 -2 -2
  30. // 6
  31. // 5 10 -5 -5 -10 -10
  32.  
  33.  
  34.  
  35.  
  36.  
  37. vector<int> a;
  38.  
  39. int consistency1(int n){
  40.  
  41. 	int ans = 0;
  42.  
  43. 	for(int i=0; i<=n-4; i++){
  44. 		for(int j=i+1; j<=n-3; j++){
  45.  
  46. 			unordered_map<int,int> sufixMp;
  47. 			for(int k=n-1; k>=j+1; k--){
  48. 				sufixMp[a[k]]++;
  49. 			}
  50.  
  51. 			for(int k=j+1; k<=n-2; k++){
  52. 				sufixMp[a[k]]--;
  53. 				if(sufixMp[a[k+1]] == 0) sufixMp.erase(a[k]);
  54.  
  55. 				int sum = a[i] + a[j] + a[k];
  56.  
  57. 				if(sufixMp.count(-sum)){
  58. 					ans += sufixMp[-sum];
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	return ans;
  65. }
  66.  
  67.  
  68.  
  69.  
  70.  
  71. int consistency2(int n){
  72.  
  73. 	int ans = 0;
  74.  
  75. 	sort(begin(a), end(a));
  76.  
  77. 	for(int i=0; i<=n-4; i++){
  78. 		for(int j=i+1; j<=n-3; j++){
  79.  
  80. 			int sum = a[i]+a[j];
  81.  
  82. 			int t = -sum;
  83.  
  84. 			int s = j+1, e = n-1;
  85. 			while(s<e){
  86. 				if(a[s] + a[e] == t){
  87.  
  88. 					//* t = 8   [4 4 4 4 4 ] => 5C2 
  89. 					if(a[s] == a[e]){
  90. 						int ct = e-s+1;
  91. 						ans += (ct*(ct-1))/2;
  92. 						break;
  93. 					}
  94.  
  95. 					int ct1 = 0;
  96. 					int x1 = a[s];
  97. 					while(s<=e && a[s] == x1){
  98. 						ct1++;
  99. 						s++;
  100. 					}
  101.  
  102. 					int ct2 = 0;
  103. 					int x2 = a[e];
  104. 					while(s<=e && a[e] == x2){
  105. 						ct2++;
  106. 						e--;
  107. 					}
  108.  
  109. 					ans += ct1 * ct2;
  110. 				}
  111. 				else if(a[s] + a[e] > t) e--;
  112. 				else s++;
  113. 			}
  114.  
  115. 		}
  116. 	}
  117.  
  118. 	return ans;
  119. }
  120.  
  121.  
  122.  
  123.  
  124.  
  125. int consistency3(int n){
  126.  
  127. 	int ans = 0;
  128.  
  129. 	unordered_map<int,int> mp;
  130. 	for(int i=n-1; i>=2; i--){
  131. 		for(int j=i-1; j>=1; j--){
  132. 			mp[a[i]+a[j]]++;
  133. 		}
  134. 	}
  135.  
  136. 	for(int j=1; j<=n-3; j++){
  137.  
  138. 		for(int k=j+1; k<=n-1; k++){
  139. 			int sum = a[j]+a[k];
  140.  
  141. 			mp[sum]--;
  142. 			if(mp[sum] == 0) mp.erase(sum);
  143. 		}
  144.  
  145. 		for(int i=j-1; i>=0; i--){
  146.  
  147. 			int sum = a[i]+a[j];
  148. 			if(mp.count(-sum))	ans += mp[-sum];
  149. 		}
  150. 	}
  151.  
  152.  
  153. 	return ans;
  154. }
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. int practice(int n){
  180.  
  181. 	int ans = 0;
  182.  
  183.  
  184.  
  185.  
  186.     return ans;
  187. }
  188.  
  189.  
  190.  
  191.  
  192.  
  193. void solve() {
  194.  
  195.     int n;
  196.     cin>> n;
  197.  
  198.     a.resize(n);
  199.     for(int i=0; i<n; i++) cin >> a[i];
  200.  
  201.     cout << consistency1(n) << " " << consistency2(n) << " " << consistency3(n) << endl;
  202.  
  203.     // cout << " => " << practice(n) << endl;
  204.  
  205.  
  206. }
  207.  
  208.  
  209.  
  210.  
  211.  
  212. int32_t main() {
  213.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  214.  
  215.     int t = 1;
  216.     cin >> t;
  217.     while (t--) {
  218.         solve();
  219.     }
  220.  
  221.     return 0;
  222. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
2
7
1 2 3 4 -1 -2 -2
6
5 10 -5 -5 -10 -10
stdout
copy 
3 3 3
4 4 4
https://ideone.com/iInve8
language:
C++14 (gcc 8.3)
created:
4 hours 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!