Submission #6364100

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 100 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n, m;
int a[N];

bool read() {
    if (!(cin >> n >> m))
        return false;

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    return true;
}

void solve() {
    map<int, int> f;
    auto ans = 0;

    for (int i = 0; i < n; ++i)
        if (a[i] % m != 0)
            ++f[a[i]];
        else
            ++ans;

    ans /= 2;
    map<int, int> g, p;

    for (auto i : f) {
        p[i.first % m] += i.second / 2;
        ans += i.second / 2;

        if (i.second & 1)
            ++g[i.first % m];
    }

    vector<int> keys;

    for (auto i : g)
        keys.emplace_back(i.first);

    for (auto i : keys)
        while (g[i] >= 2 && p[(m - i) % m] > 0) {
            g[i] -= 2;
            --p[(m - i) % m];
            ++ans;
        }

    for (auto i : keys)
        if (i + i < m)
            ans += min(g[i], g[(m - i) % m]);

    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}

Submission Info

Judge Result