Submission #7183130

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

vector<ll> cnt(101010, 0);
vector<ll> mo(101010, 0);

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

    ll N, M;
    cin >> N >> M;

    vector<ll> X(N);
    REP(i, N) cin >> X[i];

    REP(i, N) cnt[X[i]]++;
    REP(i, 101010) mo[i%M] += cnt[i];
    
    ll res = 0;
    res += mo[0]/2;
    if(M%2==0) res += mo[M/2]/2;

	REP(i, (M-1)/2){
		int x = i+1;
		int y = M-x;
		ll sumx = mo[x],sumy = mo[y];
		if(sumx > sumy) swap(x, y), swap(sumx, sumy);
		//dump(x) dump(y)
		for(int k=y;k<101010;k+=M){
			while(cnt[k]>=2 && sumy-2 >= sumx){
				cnt[k] -= 2;
				sumy -= 2;
				res++;
			}
		}
		res += sumx;
		//dump(res)
	}
	cout << res << endl;
    return 0;
}

Submission Info

Judge Result