Submission #993729

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <numeric>
#include <deque>
#include <limits>
#include <set>
#include <map>
using namespace std;

int n, m;
vector<int> x;
vector<deque<int>> dic;
vector<int> cnt;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while (cin >> n >> m) {
        dic.assign(m, {});
        cnt.assign(100010, 0);
        x.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        sort(x.begin(), x.end());
        for (int i = 0; i < n; i++) {
            dic[x[i] % m].push_back(x[i]);
            ++cnt[x[i]];
        }
        for (int i = 0; i < m; i++) {
            sort(dic[i].begin(), dic[i].end(), [&](int a, int b) {
                return cnt[a] % 2 > cnt[b] % 2;
            });
        }

        int ans = 0;

        for (int i = 0; i <= m / 2; i++) {
            if (i == m - i || i == 0) {
                int p = dic[i].size() / 2;
                ans += p;
                for (int j = 0; j < p; j++) {
                    --cnt[dic[i].front()];
                    dic[i].pop_front();
                    --cnt[dic[i].front()];
                    dic[i].pop_front();
                }
            } else {
                int p = min(dic[i].size(), dic[m - i].size());
                ans += p;
                for (int j = 0; j < p; j++) {
                    --cnt[dic[i].front()];
                    dic[i].pop_front();
                    --cnt[dic[m - i].front()];
                    dic[m - i].pop_front();
                }
            }
        }

        for (int i = 0; i <= 100000; i++) {
            ans += cnt[i] / 2;
        }

        cout << ans << endl;
    }

}

Submission Info

Judge Result