algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }