Submission #993158

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}
	Scanner cin;
	const int MOD = 1000000007;
	const int INF = int.MaxValue - 10;
	const long INFL = long.MaxValue - 10;
	const double EPS = 1e-7;
	const double PI = 3.1415926536;

	int N,M;
	int[] X;
	int[] num, pair;

	void prog()
	{
		cin = new Scanner();
		int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		N = cin.nextInt();	// 10^5
		M = cin.nextInt();  // 10^5
		num = new int[M];
		pair = new int[M];

		X = new int[N];
		for (int i = 0; i < N; i++)
		{
			X[i] = cin.nextInt();   // 10^5
			num[X[i] % M]++;
		}
		// ペア後回し
		Array.Sort(X);
		for (int i = 0; i < N - 1; i++)
		{
			if (X[i] == X[i + 1])
			{
				pair[X[i] % M]++;
				i++;
			}
		}
		long ans = 0;
		for (int i = 1; i < (M + 1) / 2; i++)
		{
			if (num[i] <= num[M - 1])
			{
				int min = num[i];
				//pair[i] = 0;
				pair[M - i] -= (Math.Max(min - (num[M - i] - pair[M - i] * 2), 0) + 1) / 2;
				ans += min;
				ans += pair[M - i];
			}
			else
			{
				int min = num[M - 1];
				pair[i] -= (Math.Max(min - (num[i] - pair[i] * 2), 0) + 1) / 2;
				//pair[M - i] = 0;
				ans += min;
				ans += pair[i];
			}
		}
		ans += num[0] / 2;
		if (M % 2 == 0)
		{
			ans += num[M / 2] / 2;
		}
		Console.WriteLine(ans);
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}
}

Submission Info

Judge Result