Submission #5538919

---

Source Code Expand

// D - Pair Cards.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <numeric>


using lolo=long long;
using namespace std;
using vec=vector<lolo>;
using vvec=vector<vec>;
using vecb=vector<bool>;
#define FOR(i,n) for (lolo i=0; i<n; ++i)
#define FORN(i,a,b) for (lolo i=a; i<b; ++i)
#define REV(i,a,b) for (lolo i=a; i>b; --i)
#define ALL(x) x.begin(), x.end()

template <class T>
void chmax(T& ans, const T& b)
{
	if (ans < b) {
		ans = b;
	}
}

int main()
{
	lolo N, M;
	cin >> N >> M;
	vec X(N);
	lolo mmax = 0;
	FOR(i, N) {
		cin >> X[i];
		chmax(mmax, X[i]);
	}

	vector< map<lolo, lolo> > POOL(M, map<lolo, lolo>{});
	//vec S(mmax + 1, 0);
	vec S(M, 0);
	
	FOR(i, N) {
		S[X[i] % M ] += 1;
		//POOL[X[i] % M].push_back(X[i]);
		POOL[X[i] % M][X[i]] += 1;
	}

	//int i = 1; int j = (M - i) % M;
	int i = 0; int j = 0;
	lolo ans = 0;
	//ans += S[0] / 2;
	while (i <= j) {
		// i == j になるのは、Mが偶数の時
		if (i != j) {
			ans += min(S[i], S[j]);
			
			lolo ones = 0;
			lolo pairs = 0;
			if (S[i] > S[j]) {
				for (auto mv : POOL[ i % M]) {
					ones += (mv.second % 2 == 1) ? 1 : 0;
					pairs += mv.second / 2;
				}
			}
			else {
				for (auto mv : POOL[ j % M]) {
					ones += (mv.second % 2 == 1) ? 1 : 0;
					pairs += mv.second / 2;
				}
			}

			lolo rem = min(S[i], S[j]) - ones;
			if (rem > 0) {// ones が足りないとき
				pairs -= (rem + 1) / 2;
			}
			ans += pairs ;

			
		}
		else if ( i == j and i == 0) {
			lolo ones = 0, pairs = 0;
			for (auto mv : POOL[j  % M]) {
				ones += (mv.second % 2 == 1) ? 1 : 0;
				pairs += mv.second / 2;
			}
			//lolo rem = max(S[i], S[j]) - min(S[i], S[j]);
			//ans += pairs / 2;
			ans += S[i] / 2;
		}
		else {
			//lolo rem = max(S[i], S[j]) - min(S[i], S[j]);
			ans += S[i] / 2;

		}
		
		i += 1;
		(j = (j + M) - 1) %= M;
	}
	cout << ans << endl;

}

Submission Info

Judge Result