LcVRPContest/DifferenceCalc.cpp at master · plawinskig/LcVRPContest · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "DifferenceCalc.hpp"

DifferenceCalc::DifferenceCalc(int num_groups, int num_nodes)
    : group_sizes_vect1_(std::vector<int>(num_groups)),
    group_sizes_vect2_(std::vector<int>(num_groups)),
    intersection_matrix_(std::vector<int>(num_groups * num_groups)),
    num_nodes_(num_nodes),
    num_groups_(num_groups),
    matrix_total_size_(num_groups * num_groups),
    total_possible_pairs_((static_cast<long long>(num_nodes) * (num_nodes - 1)) >> 1)
{
    active_intersection_indices_.reserve(num_nodes);
}

long long DifferenceCalc::calcDifference(const std::vector<int> &vect1, const std::vector<int> &vect2)
{
    for (size_t i = 0; i < num_nodes_; ++i)
    {
        int group1 = vect1[i];
        int group2 = vect2[i];

        ++group_sizes_vect1_[group1];
        ++group_sizes_vect2_[group2];

        int matrix_idx = group1 * num_groups_ + group2;

        if (intersection_matrix_[matrix_idx] == 0)
        {
            active_intersection_indices_.push_back(matrix_idx);
        }

        ++intersection_matrix_[matrix_idx];
    }

    long long pairs_within_vect1 = 0;
    long long pairs_within_vect2 = 0;

    for (int i = 0; i < num_groups_; ++i)
    {
        if (group_sizes_vect1_[i] > 1)
        {
            pairs_within_vect1 += calculatePairsFromGroupSize(group_sizes_vect1_[i]);
        }
        group_sizes_vect1_[i] = 0;

        if (group_sizes_vect2_[i] > 1)
        {
            pairs_within_vect2 += calculatePairsFromGroupSize(group_sizes_vect2_[i]);
        }
        group_sizes_vect2_[i] = 0;
    }

    long long pairs_shared = 0;

    for (int idx : active_intersection_indices_)
    {
        int intersection_count = intersection_matrix_[idx];

        if (intersection_count > 1)
        {
            pairs_shared += calculatePairsFromGroupSize(intersection_count);
        }

        intersection_matrix_[idx] = 0;
    }

    active_intersection_indices_.clear();

    long long difference = pairs_within_vect1 + pairs_within_vect2 - 2 * pairs_shared;

    return difference;
}