main.cpp (3164B)
1 #include <iostream> 2 #include <unordered_map> 3 #include <vector> 4 5 long long score(std::vector<long long>& eles) { 6 long long currentSum = 0; 7 long long res = 0; 8 for(int i = 0; i < eles.size(); ++i) { 9 currentSum += eles[i]; 10 if(currentSum == 0) { 11 res += 1; 12 } 13 } 14 return res; 15 } 16 17 int main() { 18 int tc = 0; 19 std::cin >> tc; 20 for(int i = 0; i < tc; ++i) { 21 long long len = 0; 22 std::cin >> len; 23 std::vector<long long> eles {}; 24 25 for(int x = 0; x < len; ++x) { 26 int cur = 0; 27 std::cin >> cur; 28 eles.push_back(cur); 29 } 30 31 // compute prefix sum from start -> first zero 32 // this is always done 33 34 std::vector<long long> workingPrefixes {}; 35 long long currentSum = 0; 36 int idx = 0; 37 int lastKnownZeroIdx = eles.size(); 38 39 while (idx < eles.size() && eles[idx] != 0) { 40 currentSum += eles[idx]; 41 workingPrefixes.push_back(currentSum); 42 idx += 1; 43 } 44 45 if (idx < eles.size() && eles[idx] == 0) { 46 lastKnownZeroIdx = idx; 47 } 48 49 50 // if a zero was found, we then go from there to the next zero 51 // computing prefix sums, find the most common element, and set the 52 // first zero to the aditive inverse 53 54 55 while(idx < eles.size()) { 56 57 if(idx == lastKnownZeroIdx) { 58 idx += 1; 59 workingPrefixes.push_back(currentSum); 60 continue; 61 } 62 if(eles[idx] == 0) { 63 64 65 std::unordered_map<long long,long long> frequencies {}; 66 long long mostCommon = 0; 67 long long count = 0; 68 for(int m = lastKnownZeroIdx; m < idx; ++m) { 69 frequencies[workingPrefixes[m]] += 1; 70 long long freq = frequencies[workingPrefixes[m]]; 71 if(freq > count) { 72 count = freq; 73 mostCommon = workingPrefixes[m]; 74 } 75 } 76 eles[lastKnownZeroIdx] = mostCommon * -1; 77 78 currentSum += eles[lastKnownZeroIdx]; 79 workingPrefixes.push_back(currentSum); 80 81 lastKnownZeroIdx = idx; 82 idx += 1; 83 continue; 84 } 85 86 currentSum += eles[idx]; 87 workingPrefixes.push_back(currentSum); 88 idx += 1; 89 } 90 if (lastKnownZeroIdx < (int)eles.size()) { 91 std::unordered_map<long long, long long> frequencies{}; 92 long long mostCommon = 0; 93 long long count = 0; 94 for (int m = lastKnownZeroIdx; m < (int)eles.size(); ++m) { 95 frequencies[workingPrefixes[m]] += 1; 96 long long freq = frequencies[workingPrefixes[m]]; 97 if (freq > count) { 98 count = freq; 99 mostCommon = workingPrefixes[m]; 100 } 101 } 102 eles[lastKnownZeroIdx] = mostCommon * -1; 103 } 104 105 std::cout << score(eles) << std::endl; 106 } 107 108 }