algorithms

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

main.cpp (1870B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 
     13 // - idea:
     14 // - compute all pairs
     15 //     - compute the sums and then creates sets of matches where we encode this as a list of indexes that start these triads
     16 //         - we can then perform some basic match to compute intersections and such within groups
     17 //             - is this too costly? assume there's a case where ~200_000 sums match, we then do a o(n^2) op to compare them all
     18 // - on insertions we could add the number of additional matches we get to some sum
     19 //     - that seems better.
     20 //     - so when inserting the first element we add none
     21 //     - when inserting the second element we add 1 iff they are disjoint
     22 //     - we then proceed as such.
     23 
     24 int main() {
     25 
     26     int testCases, n, cn;
     27     cin >> testCases;
     28 
     29     for(int z = 0; z < testCases; ++z) {
     30         cin >> n;
     31         vector<int> ls (n,0);
     32 
     33         for(int i = 0; i < n; ++i) {
     34             cin >> cn;
     35             ls[i] = cn;
     36         }
     37 
     38         long long res = 0;
     39 
     40         unordered_map<int, unordered_set<int>> triadScores {};
     41 
     42         for(int i = 0; i < n-4; ++i) {
     43             int score = (ls[i] + ls[i+2]) - ls[i+4];
     44             if(!triadScores.contains(score)) {
     45                 unordered_set<int> current {};
     46                 current.insert(i);
     47                 triadScores[score] = current;
     48             } else {
     49 
     50                 int count = triadScores[score].size();
     51                 triadScores[score].insert(i);
     52                 if(triadScores[score].contains(i-2)) {
     53                     count -= 1;
     54                 }
     55 
     56                 if(triadScores[score].contains(i-4)) {
     57                     count -= 1;
     58                 }
     59                 res += count;
     60             }
     61         }
     62 
     63         cout << res << endl;
     64 
     65     }
     66 }