fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. int main() {
  5. 	ios_base::sync_with_stdio(0);
  6. 	cin.tie(NULL);
  7. 	cout.tie(NULL);
  8. 	ll t;
  9. 	cin >> t;
  10. 	while (t--) {
  11.  
  12. 		ll n;
  13. 		cin >> n;
  14.  
  15. 		ll arr[n];
  16. 		ll four = -1;
  17. 		ll ans = 0;
  18. 		ll f_index = -1;
  19. 		bool tr = true;
  20. 		for (ll i = 0; i < n; i++) {
  21. 			cin >> arr[i];
  22. 			arr[i] = abs(arr[i]);
  23. 			arr[i] = arr[i] % 4;
  24. 			if (arr[i] == 0) {
  25. 				if (tr) {
  26. 					f_index = i;
  27. 					tr = false;
  28. 				}
  29. 				ans++;
  30. 			}
  31. 			if (arr[i] == 1 || arr[i] == 3) {
  32. 				ans++;
  33. 			}
  34.  
  35.  
  36. 		}
  37.  
  38.  
  39. 		ll two_index = -1;
  40. 		ll odd_index = -1;
  41. 		ll two_index_two = -1;
  42. 		ll tf = 0;
  43. 		for (ll i = 0; i < n; i++) {
  44.  
  45. 			if (arr[i] == 0) {
  46.  
  47. 				four = i;
  48. 				ans += (i - 0);
  49. 			}
  50. 			if (arr[i] == 2) {
  51.  
  52. 				if (four == -1 && two_index != -1) {
  53. 					ans += two_index + 1;
  54. 				}
  55. 				else if (four != -1 && two_index == -1) {
  56.  
  57. 					ans += four + 1;
  58. 				}
  59. 				else if (four != -1 && two_index != -1) {
  60. 					ans += max(four, two_index) + 1;
  61. 				}
  62. 				two_index_two = two_index;
  63. 				two_index = i;
  64. 				tf++;
  65.  
  66.  
  67. 			}
  68. 			if (arr[i] == 3 || arr[i] == 1) {
  69.  
  70. 				if (tf >= 2 && four != -1) {
  71.  
  72. 					if (four > two_index) {
  73. 						ans += four + 1;
  74. 						ans += i - four - 1;
  75. 					}
  76. 					else if (four < two_index && four > two_index_two) {
  77.  
  78. 						ans += i - two_index - 1;
  79. 						ans += four + 1;
  80. 					} else if (four < two_index && four < two_index_two) {
  81.  
  82. 						ans += i - two_index - 1;
  83. 						ans += two_index_two + 1;
  84. 					}
  85.  
  86.  
  87. 				} else if (tf == 1 && four != -1) {
  88.  
  89. 					if (four < two_index) {
  90.  
  91. 						ans += four + 1;
  92. 						ans += i - two_index - 1;
  93. 					} else if (four > two_index) {
  94.  
  95. 						ans += four + 1;
  96. 						ans += i - four - 1;
  97. 					}
  98.  
  99. 				} else if (tf >= 2 && four == -1) {
  100.  
  101. 					ans += i - two_index - 1;
  102. 					ans += two_index_two + 1;
  103.  
  104.  
  105. 				} else if (tf == 1 && four == -1) {
  106.  
  107. 					ans += i - two_index - 1;
  108.  
  109.  
  110. 				} else if (tf == 0 && four != -1) {
  111.  
  112. 					ans += i - four - 1;
  113. 					ans += four + 1;
  114. 				} else if (tf == 0 && four == -1) {
  115. 					ans += i ;
  116. 				}
  117.  
  118.  
  119.  
  120. 			}
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127. 		}
  128.  
  129. 		cout << ans << '\n';
  130. 	}
  131.  
  132. }
  133.  
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
2
3
1 2 3
3
2 5 6
stdout
copy 
2
2
https://ideone.com/byz7yC
language:
C++14 (gcc 8.3)
created:
5 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!