# Untitled

a guest
Feb 12th, 2022
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
5. #define F(i, n) for(int i = 0; i < n; i++)
6.
7. using ll = long long;
8. using vi = vector<int>;
9. using pii = pair<int, int>;
10.
11. const int LIMIT_INT = 1e5+5, LIMIT_LLONG = 1e9+5;
12. const long long MOD = 1e9+7;
13. int tests, n;
14.
15. void solve()
16. {
17. cin>>n;
18. vi rocks(n);
19. int high_odd = -1, high_even = -1;
20. F(i, n) {
21. cin>>rocks[i];
22. if(i > 0 && i < (n - 1)) {
23. if(rocks[i] % 2 && rocks[i] > 1) high_odd = i;
24. else if(rocks[i] % 2 == 0 && rocks[i] > 1) high_even = i;
25. }
26. }
27. if(n == 3) {
28. if(rocks[1] % 2) cout<<"-1\n";
29. else cout<<rocks[1] / 2<<"\n";
30. } else if(rocks[n - 2] == 1 && high_odd == -1 && high_even == -1) {
31. cout<<"-1\n";
32. }
33. else {
34. int last_odd = -1;
35. int last_even = -1;
36. ll op = 0;
37.
38. if(rocks[n - 2] == 1) {
39. if(high_even > -1) rocks[high_even] -= 2;
40. else if(high_odd > -1) rocks[high_odd] -= 2;
41. op++;
42. rocks[n - 2] = 2;
43. }
44.
45. for(int i = n - 2; i >= 1; i--) {
46. if(rocks[i] % 2) {
47. if(last_even == -1 && last_odd == -1) last_odd = i;
48. else if(last_odd > -1) {
49. rocks[i]--;
50. rocks[last_odd]--;
51. op += 2;
52. last_even = last_odd;
53. last_odd = -1;
54. } else if(last_even > -1) {
55. rocks[i]++;
56. rocks[last_even] -= 2;
57. op++;
58. last_even = i;
59. }
60. } else {
61. if(last_odd > -1) {
62. rocks[i] -= 2;
63. rocks[last_odd]++;
64. op++;
65. last_even = last_odd;
66. last_odd = -1;
67. } else last_even = i;
68. }
69. }
70.
71. for(int i = n - 2; i >= 1; i--) {
72. op += (rocks[i] / 2);
73. }
74.
75. cout<<op<<"\n";
76. }
77. }
78.
79. int main() {
80. fast_io;
81. cin>>tests;
82. while(tests--) solve();
83. return 0;
84. }
85.
86.