Submission #993517

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;} cout << endl;
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
typedef vvi Graph;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    cin >> n >> m;
    vi x(n);
    rep(i, n) cin >> x[i];

    auto c = [](int l, int r) {
        // 奇数の方が先、どちらも偶数なら小さい方が先
        if (l % 2) return true;
        else if (r % 2) return false;
        else return l < r;
    };
    using PQ = priority_queue<int, vector<int>, decltype(c)>;
    // xをmodで分類
    vector<PQ> y(m, PQ(c));
    rep(i, n) {
        y[x[i] % m].push(x[i]);
    }

    int ans = y[0].size() / 2;
    if (m % 2 == 0) ans += y[m/2].size() / 2;
    rep2(i, 1, (m + 1) / 2) {
        while (!y[i].empty() && !y[m-i].empty()) {
            y[i].pop();
            y[m-i].pop();
            ans++;
        }
    }

    rep(i, m) {
        if (i == 0 || 2 * i == m) continue;
        map<int, int> mp;
        while (!y[i].empty()) {
            mp[y[i].top()]++;
            y[i].pop();
        }
        for (auto p : mp) {
            ans += p.second / 2;
        }
    }

    // rep(i, m) {
    //     cerr << i << ":";
    //     while (!y[i].empty()) {
    //         cerr << y[i].top() << " ";
    //         y[i].pop();
    //     }
    //     cerr << endl;
    // }

    cout << ans << endl;
}

Submission Info

Judge Result