Return to Answer

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the mods occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> mods;
    std::for_each(v.begin(), v.end(), [&mods,k](auto& x) {++mods[x%k];});
    int subset_size{0};
    // 0 and k/2 mods can only be included once
    auto zero_mod = mods.find(0);
    if (zero_mod != mods.end()) {
        ++subset_size;
        mods.erase(zero_mod);
    }
    if (k%2 == 0) {
        auto half_k_mod = mods.find(k/2);
        if (half_k_mod != mods.end()) {
            ++subset_size;
            mods.erase(half_k_mod);
        }
    }
    if (mods.begin() == mods.end()) return subset_size;
    // For each mod x there is only other mod x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair count the one with more ocurrencies.
    if (mods.size()==1) return subset_size += mods.begin()->second;
    auto bottom_up = mods.begin();
    auto top_down = mods.rbegin();
    while (bottom_up->first <= top_down->first) {
        if (bottom_up->first + top_down->first == k) {
            subset_size += std::max(bottom_up->second,top_down->second);
            ++bottom_up, ++top_down;
        }
        // if not complementary addvance count and advance the outter one
        else if (top_down->first < k - bottom_up->first) {
            subset_size += mods[bottom_up->first];
            ++bottom_up;
        }
        else {
            subset_size += mods[top_down->first];
            ++top_down;
        }
    }
    return subset_size;
}

int main() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for(int i = 0; i < n; ++i){
       std::cin >> v[i];
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the mods occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> mods;
    std::for_each(v.begin(), v.end(), [&mods,k](auto& x) {++mods[x%k];});
    // 0 and k/2 mods can only be included once
    int subset_size{0};
    auto zero_mod = mods.find(0);
    if (zero_mod != mods.end()) {
        ++subset_size;
        mods.erase(zero_mod);
    }
    if (k%2 == 0) {
        auto half_k_mod = mods.find(k/2);
        if (half_k_mod != mods.end()) {
            ++subset_size;
            mods.erase(half_k_mod);
        }
    }
    if (mods.begin() == mods.end()) return subset_size;
    // For each mod x there is only other mod x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair count the one with more ocurrencies.
    if (mods.size()==1) return subset_size += mods.begin()->second;
    auto bottom_up = mods.begin();
    auto top_down = mods.rbegin();
    while (bottom_up->first <= top_down->first) {
        if (bottom_up->first + top_down->first == k) {
            subset_size += std::max(bottom_up->second,top_down->second);
            ++bottom_up, ++top_down;
        }
        // if not complementary count and advance the outter one
        else {
            if (top_down->first < k - bottom_up->first) {
                subset_size += mods[bottom_up->first];
                ++bottom_up;
            }
            else {
                subset_size += mods[top_down->first];
                ++top_down;
            }
        }
    }
    return subset_size;
}

int main() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for(int i = 0; i < n; ++i){
       std::cin >> v[i];
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

I've tried to solve the problem avoiding sorting, but still, it runs too slow to pass the test.

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the remainders occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> remainders;
    for (auto e : v) {
        int r = e%k;
        ++remainders[r];
    }
    int subset_size{0};
    // 0 and k/2 remainders can only be included once
    auto zero_remainder = remainders.find(0);
    if ( zero_remainder != remainders.end()) {
        ++subset_size;
        remainders.erase(zero_remainder);
    }
    if (k%2 == 0) {
        auto half_k_remainder = remainders.find(k/2);
        if (half_k_remainder != remainders.end()) {
            ++subset_size;
            remainders.erase(half_k_remainder);
        }
    }
    // For each remainder x there is only other remainder x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair, count the one with more ocurrencies.
    for (auto it = remainders.begin(); it->first <= k/2; ++it) {
        auto it_complement = remainders.find(it->first - k);
        if (it_complement != remainders.end()) {
            subset_size += std::max(it->second,it_complement->second);
        }
        else {
            subset_size += it->second;
        }
    }
    return subset_size;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    while(n--) {
        int x; std::cin >> x;
        v.push_back(x);
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

I've finally made it work

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the mods occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> mods;
    std::for_each(v.begin(), v.end(), [&mods,k](auto& x) {++mods[x%k];});
    int subset_size{0};
    // 0 and k/2 mods can only be included once
    auto zero_mod = mods.find(0);
    if (zero_mod != mods.end()) {
        ++subset_size;
        mods.erase(zero_mod);
    }
    if (k%2 == 0) {
        auto half_k_mod = mods.find(k/2);
        if (half_k_mod != mods.end()) {
            ++subset_size;
            mods.erase(half_k_mod);
        }
    }
    if (mods.begin() == mods.end()) return subset_size;
    // For each mod x there is only other mod x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair count the one with more ocurrencies.
    if (mods.size()==1) return subset_size += mods.begin()->second;
    auto bottom_up = mods.begin();
    auto top_down = mods.rbegin();
    while (bottom_up->first <= top_down->first) {
        if (bottom_up->first + top_down->first == k) {
            subset_size += std::max(bottom_up->second,top_down->second);
            ++bottom_up, ++top_down;
        }
        // if not complementary addvance count and advance the outter one
        else if (top_down->first < k - bottom_up->first) {
            subset_size += mods[bottom_up->first];
            ++bottom_up;
        }
        else {
            subset_size += mods[top_down->first];
            ++top_down;
        }
    }
    return subset_size;
}

int main() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for(int i = 0; i < n; ++i){
       std::cin >> v[i];
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

The trick was the way to look for the pairs, the bottom_up top_down approach of papagaga was faster than finding the elements.

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    if (v.begin() == v.end()) return 0;
    // Count the remainders occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> remainders;
    for (auto e : v) {
        int r = e%k;
        ++remainders[r];
    }
    int subset_size{0};
    // 0 and k/2 remainders can only be included once
    auto zero_remainder = remainders.find(0);
    if (zero_remainder != remainders.end()) {
        ++subset_size;
        remainders.erase(zero_remainder);
    }
    auto half_k_remainder = remainders.find(k/2);
    if (half_k_remainder != remainders.end()) {
        ++subset_size;
        remainders.erase(half_k_remainder);
    }
    if (remainders.begin() == remainders.end()){
        return subset_size;
    }
    // For each remainder x there is only other remainder x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair, count the one with more ocurrencies.
    for (auto it = remainders.begin(); it->first <= k/2; ++it) {
        auto it_complement = remainders.find(it->first - k);
        if (it_complement != remainders.end()) {
            subset_size += std::max(it->second,it_complement->second);
        }
        else {
            subset_size += it->second;
        }
    }
    return subset_size;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    while(n--) {
        int x; std::cin >> x;
        v.push_back(x);
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the remainders occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> remainders;
    for (auto e : v) {
        int r = e%k;
        ++remainders[r];
    }
    int subset_size{0};
    // 0 and k/2 remainders can only be included once
    auto zero_remainder = remainders.find(0);
    if ( zero_remainder != remainders.end()) {
        ++subset_size;
        remainders.erase(zero_remainder);
    }
    if (k%2 == 0) {
        auto half_k_remainder = remainders.find(k/2);
        if (half_k_remainder != remainders.end()) {
            ++subset_size;
            remainders.erase(half_k_remainder);
        }
    }
    // For each remainder x there is only other remainder x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair, count the one with more ocurrencies.
    for (auto it = remainders.begin(); it->first <= k/2; ++it) {
        auto it_complement = remainders.find(it->first - k);
        if (it_complement != remainders.end()) {
            subset_size += std::max(it->second,it_complement->second);
        }
        else {
            subset_size += it->second;
        }
    }
    return subset_size;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    while(n--) {
        int x; std::cin >> x;
        v.push_back(x);
    }
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}