Submission #994531

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
	int n, m;
	cin >> n >> m;

	vector<int> v(n);
	rep(i, n) cin >> v[i];
	sort(v.begin(), v.end());

	map<int, int> ma;
	rep(i, n) {
		ma[v[i]]++;
	}

	priority_queue<P, vector<P>, greater<P> > que[100005];
	each(it, ma) {
		int mm = it->first % m;

		if(it->second % 2 == 0) {
			que[mm].push(mp(it->second, it->first));
		} else {
			que[mm].push(mp((-1) * it->second, it->first));
		}
		// cout << it->first << " " << it-> second << " m;" << mm << endl;;
	}

	int ans = 0;
	REP(i, 1, m / 2 + (m % 2 != 0)) { //0は例外
		int j = m - i;

		// cout << "----------in for:" << i << " " << j << endl;

		while(que[i].size() && que[j].size()) {
			P p1 = que[i].top(); que[i].pop();
			P p2 = que[j].top(); que[j].pop();

			if(p1.first < 0) {
				p1.first *= -1;
			}
			if(p2.first < 0) {
				p2.first *= -1;
			}

			// cout << "p1:" << p1.first << " " << p1.second << endl;
			// cout << "p2:" << p2.first << " " << p2.second << endl;

			if(p1.first >= p2.first) {
				ans += p2.first;
				ma[p1.second] -= p2.first;
				ma[p2.second] -= p2.first;

				p1.first -= p2.first;
				p2.first = 0;

				if(p1.first > 0) {
					if(p1.first % 2 == 0) {
						que[i].push(mp(p1.first, p1.second));
					} else {
						que[i].push(mp((-1) * p1.first, p1.second));
					}
					// cout << " -- update:" << p1.first << " " << p1.second << endl;
				}
			} else {
				ans += p1.first;
				ma[p1.second] -= p1.first;
				ma[p2.second] -= p1.first;

				p2.first -= p1.first;
				p1.first = 0;

				if(p2.first > 0) {
					if(p2.first % 2 == 0) {
						que[j].push(mp(p2.first, p2.second));
					} else {
						que[j].push(mp((-1) * p2.first, p2.second));
					}
					// cout << " -- update:" << p2.first << " " << p2.second << endl;
				}
			}
		}
	}

	int sum = 0;
	while(que[0].size()) {
		P p = que[0].top(); que[0].pop();
		if(p.first < 0) {
			p.first *= -1;
		}
		sum += p.first;
		ma[p.second] = 0;
	}

	ans += sum / 2;

	each(it, ma) {
		// cout << "end:" << it->first << " " << it->second << endl;
		if(it->second >= 2) {
			ans += it->second / 2;
		}
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result