Problem:


Score : 700 points

Problem Statement

Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

The integers on the two cards are the same.

The sum of the integers on the two cards is a multiple of M.

Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

2≦N≦10^5

1≦M≦10^5

1≦X_i≦10^5

Input

The input is given from Standard Input in the following format:

N M
X_1 X_2 ... X_N

Output

Print the maximum number of pairs that can be created.

Sample Input 1

7 5
3 1 4 1 5 9 2

Sample Output 1

3

Three pairs (3,2), (1,4) and (1,9) can be created.

It is possible to create pairs (3,2) and (1,1), but the number of pairs is not maximized with this.

Sample Input 2

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99

Sample Output 2

6



Sample input:
7 5
3 1 4 1 5 9 2


Sample output:
3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import Counter,defaultdict
def resolve():
    n,m=map(int,input().split())
    D=defaultdict(list)
    for a in map(int,input().split()):
        D[a%m].append(a)

    ans=len(D[0])//2
    if(m%2==0): ans+=len(D[m//2])//2

    for i in range(1,(m-1)//2+1):
        A=D[i]; B=D[m-i]
        if(len(A)<len(B)): A,B=B,A # len(A)>=len(B)
        n=len(B)
        ans+=n
        A=Counter(A).most_common()[::-1]
        for i in range(len(A)):
            if(n>0 and A[i][1]&1):
                n-=1
                A[i]=(A[i][0],A[i][1]-1)
        for key,val in A:
            if(n>=val): n-=val
            else:
                val-=n
                n=0
                ans+=val//2
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n,m=map(int,input().split())
    x=list(map(int,input().split()))
    x=ct(x)
    pair=dict()
    single=dict()
    for i,j in x.items():
        mod=i%m
        sho=j//2
        amari=j%2
        if sho>0:
            if mod in pair.keys():
                pair[mod]+=sho*2
            else:
                pair[mod]=sho*2
        if amari==1:
            if mod in single.keys():
                single[mod]+=amari
            else:
                single[mod]=amari
    ans=0
    for i in range(m//2+1):
        j=(m-i)%m
        if i==j:
            if i in single.keys():
                ans+=single[i]//2
                single[i]%=2
        else:
            if (i in single.keys()) and (j in single.keys()):
                temp=min(single[i],single[j])
                ans+=temp
                single[i]-=temp
                single[j]-=temp
    for i in single.keys():
        j=(m-i)%m
        if j in pair.keys():
            temp=min(single[i],pair[j])
            pair[j]-=temp
            ans+=temp
    for i in pair.values():
        ans+=i//2
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split())
X = [int(i) for i in input().split()]

c = Counter(X)
cm = [[0, 0] for _ in range(M)]
for k, v in c.items() :
    cm[k % M][0] += v
    cm[k % M][1] += v // 2

ret = cm[0][0] // 2
for i in range(1, (M + 1) // 2) :
    ret += min(cm[i][0], cm[M-i][0])
    if cm[i] >= cm[M-i] :
        ret += min((cm[i][0] - cm[M-i][0]) // 2, cm[i][1])
    else :
        ret += min((cm[M-i][0] - cm[i][0]) // 2, cm[M-i][1])
        
if M % 2 == 0 :
    ret += cm[M//2][0] // 2
    
print(ret)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
X = list(map(int,input().split()))
D = [ [] for _ in range(M+1) ]
for x in X:
  D[ x % M ].append(x)
ans = 0

import collections
def count_pair(A):
  res = 0
  c = collections.Counter(A)
  for k, v in c.items():
    res += v // 2
  return res

ans += len(D[0]) // 2
for x in range(1, M):
  y = M - x
  if x < y:
    D[x].sort()
    D[y].sort()
    g = min(len(D[x]), len(D[y]))
    ans += g
    if len(D[x]) > len(D[y]):
      ans += min((len(D[x]) - g) // 2, count_pair(D[x]))
    else:
      ans += min((len(D[y]) - g) // 2, count_pair(D[y]))
  if x == y:
    ans += len(D[x]) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split())
x = list(map(int, input().split()))
xM = [xi % M for xi in x]

ans = 0
Cx = Counter(x)
CxM = Counter(xM)
same_num = {i: 0 for i in range(M)}
for xi in Cx.keys():
    same_num[xi % M] += Cx[xi] // 2

ans += CxM[0] // 2
for i in range(1, M // 2 + 1):
    if i * 2 == M:
        ans += CxM[i] // 2
    else:
        ans += min(CxM[i], CxM[M - i])
        if CxM[i] < CxM[M - i]:
            ans += min(same_num[M - i], (CxM[M - i] - CxM[i]) // 2)
        else:
            ans += min(same_num[i], (CxM[i] - CxM[M - i]) // 2)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, m = getList()
nums = getList()
n_mods = [0 for i in range(m)]
pair_mods = [0 for i in range(m)]
num_mods = [{} for i in range(m)]

for num in nums:
    modres = num % m
    n_mods[modres] += 1
    if num in num_mods[modres]:
        num_mods[modres][num] += 1
    else:
        num_mods[modres][num] = 1

    if num_mods[modres][num] % 2 == 0:
        pair_mods[modres] += 1

# print(n_mods)
# print(pair_mods)
ans = 0
for i in range(1, (m+1) // 2):
    left = i
    right = m - i
    ans += min(n_mods[left], n_mods[right])
    if n_mods[left] > n_mods[right]:
        ans += max(0, min(pair_mods[left], (n_mods[left] - n_mods[right]) // 2))
    else:
        ans += max(0, min(pair_mods[right], (n_mods[right] - n_mods[left]) // 2))
    # print(left, right, ans)

ans += n_mods[0] // 2
if m % 2 == 0:
    ans += n_mods[m//2] // 2

print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#受け取り、処理
	N, M = getlist()
	X = getlist()
	D = defaultdict(int)
	for i in X:
		D[i] += 1
	L = [[] for i in range(M)]
	for i in D:
		L[i % M].append(D[i])
	#計算
	ans = 0
	for i in range(1, M):
		if i != M - i:
			a1 = 0
			a2 = 0
			for j in L[i]:
				a1 += j
				a2 += int(j // 2) * 2
			b1 = 0
			b2 = 0
			for j in L[M - i]:
				b1 += j
				b2 += int(j // 2) * 2
			if a1 - a2 > b1:
				ans += b1 + a2 // 2
			elif b1 - b2 > a1:
				ans += a1 + b2 // 2
			else:
				ans += (a1 + b1) // 2
	
	ans = ans // 2
	#細かい処理、偶奇
	if M % 2 == 0:
		ans += sum(L[M // 2]) // 2
	ans += sum(L[0]) // 2
	#答え
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,m,*x=map(int,open(0).read().split())
a,b=[0]*m,[0]*m
s=set()
for i in x:
  j=i%m
  if i in s:
    s-={i}
    b[j]+=1
  else:
    s|={i}
  a[j]+=1
c=a[0]//2+(m%2<1and a[m//2]//2)
for i in range(1,m//2+m%2):
  (i,_),(j,k)=sorted((a[j],b[j])for j in(i,m-i))
  c+=i+min(j-i>>1,k)
print(c)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
r=[defaultdict(int) for i in range(M)]
for x in X:
    r[x%M][x]+=1
a=sum(r[0].values())//2
for m in range(1,-(-M//2)):
    v1,v2=sum(r[m].values()),sum(r[M-m].values())
    if v1>v2:
        p=sum([e//2 for e in r[m].values()])
        a+=v2+min(p,(v1-v2)//2)
    else:
        p=sum([e//2 for e in r[M-m].values()])
        a+=v1+min(p,(v2-v1)//2)
if M%2==0:
    a+=sum(r[M//2].values())//2
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

N, M = map(int, input().split())
X = list(map(int, input().split()))


def main():
    P = [[] for _ in range(M)]

    for x in X:
        P[x%M].append(x)

    ans = 0
    checked = [False]*M
    for m in range(M):
        if checked[m]:
            continue
        if m == 0 or m == M-m:
            ans += len(P[m])//2
        else:
            P1, P2 = P[m], P[M-m]
            L1, L2 = len(P[m]), len(P[M-m])
            if L2 > L1:
                P1, P2 = P[M-m], P[m]
                L1, L2 = len(P1), len(P2)
            
            C1 = Counter(P1)
            n = 0
            for num, c1 in C1.items():
                n += c1//2
            if L1 - n*2 <= L2:
                ans += (L1+L2)//2
            else:
                ans += L2 + n

            checked[m] = True
            checked[M-m] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
B,BB=[0]*m,[0]*m
C=collections.Counter(A)
for a in A:
  B[a%m]+=1
for c in C.keys():
  BB[c%m]+=C[c]//2
ans=B[0]//2
if m%2==0:
  ans+=B[m//2]//2
for i in range(1,(m+1)//2):
  if B[i]<B[m-i]:
    ans+=B[i]
    ans+=min(B[m-i]-B[i],2*BB[m-i])//2
  else:
    ans+=B[m-i]
    ans+=min(B[i]-B[m-i],2*BB[i])//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,m = map(int, input().split())
c = Counter(map(int, input().split()))
r = [0]*m
s = [0]*m
for k, v in c.items():
    i = k%m
    r[i] += v
    s[i] += v//2

ans = r[0]//2
for i in range(1, m):
    j = m-i
    if i > j:
        break
    elif i == j:
        ans += r[i]//2
    else:
        if r[i] < r[j]:
            i,j = j,i
        ans += r[j]
        ans += min((r[i]-r[j])//2, s[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,m = map(int, input().split())
c = Counter(map(int, input().split()))
r = [0]*m
s = [0]*m
for key, value in c.items():
    i = key%m
    r[i] += value
    s[i] += value//2
# 0
ans = r[0]//2
for i in range(1, m):
    j = m-i
    if i < j:
        if r[i] < r[j]:
            i,j = j,i
        ans += r[j]
        ans += min((r[i]-r[j])//2, s[i])
    elif i == j:
        ans += r[i] //2
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N, M = map(int, input().split())
C = Counter(map(int, input().split()))
D = [0]*M
E = [0]*M
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        if D[i] < D[j]:
            i,j = j,i
        ans += D[j]
        ans += min((D[i]-D[j])//2, E[i])
#        x = min(D[i], D[j])
#        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        #ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N, M = map(int, input().split())
C = Counter(map(int, input().split()))
#D = defaultdict(int)
#E = defaultdict(int)
D = [0]*M
E = [0]*M
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N, M = map(int, input().split())
#X = list(map(int, input().split()))
C = Counter(map(int, input().split()))
D = defaultdict(int)
E = defaultdict(int)
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
C = Counter(X)
D = defaultdict(int)
E = defaultdict(int)
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    num, m = map(int, input().split())
    data = list(map(int, input().split()))

    data.sort()
    count_data = Counter(data)

    amari_data = [0 for i in range(m)]
    overlap_amari = [0 for i in range(m)]

    for i in range(num):
        amari = data[i] % m
        amari_data[amari] += 1

    for now_num, count in count_data.items():
        if count >= 2:
            amari = now_num % m
            overlap_amari[amari] += count // 2

    # print(amari_data)
    # print(overlap_amari)

    ans = 0
    for i in range(m):
        if i == 0:
            kari = amari_data[i] // 2
            ans += kari
            amari_data[i] -= kari * 2
        else:
            kari = min(amari_data[i], amari_data[m - i])
            ans += kari
            amari_data[i] -= kari
            amari_data[m - i] -= kari

        kari = min(overlap_amari[i], amari_data[i] // 2)
        ans += kari
        overlap_amari[i] -= kari * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
m = dd(int)
d = dd(int)
for n in c:
  d[n] += 1
  m[n % M] += 1
res = 0
for i in range(M):
  temp = min(m[i], m[(M - i) % M])
  if i == (M - i) % M:
    temp = m[i] // 2
  m[i] -= temp
  m[(M - i) % M] -= temp
  res += temp
for i in range(N):
  n = c[i]
  if m[n % M] > 1:
    k = m[n % M] // 2
    if d[n] > 1:
      temp = min(d[n] // 2, k)
      res += temp
      d[n] -= temp * 2
      m[n % M] -= temp * 2
print(res)

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split())
X = list(map(int, input().split()))

modGrp = [[] for _ in range(M)]

for x in X:
    modGrp[x % M].append(x)

ans = len(modGrp[0]) // 2
modGrp[0] = []

if M % 2 == 0:
    ans += len(modGrp[M // 2]) // 2
    modGrp[M // 2] = []

for m in range(1, M // 2 + 1):
    S = modGrp[m]
    T = modGrp[M - m]

    if len(S) < len(T):
        S, T = T, S

    cnt = Counter(S)
    dis = 0
    for c in cnt.values():
        while c >= 2 and len(S) - dis * 2 > len(T):
            dis += 1
            c -= 2
            ans += 1

    ans += min(len(T), len(S) - dis * 2)
    modGrp[m] = []
    modGrp[M - m] = []

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
X = [int(x) for x in input().split()]
X.sort()
Mod = [defaultdict(int) for _ in range(M)]
for x in X:
  Mod[x % M][x] += 1
cnt = 0
cnt += sum(list(Mod[0].values())) // 2
for i in range(1, -(-M // 2)):
  v1 = sum(list(Mod[i].values()))
  v2 = sum(list(Mod[M - i].values()))
  odd1 = sum([m % 2 for m in Mod[i].values()])
  odd2 = sum([m % 2 for m in Mod[M - i].values()])
  k = min(v1, v2)
  cnt += k
  if v1 == k:
    _k = k - min(odd2, k)
    cnt += (v2 - odd2 - _k) // 2
  else:
    _k = k - min(odd1, k)
    cnt += (v1 - odd1 - _k) // 2
if M % 2 == 0:
  cnt += sum(list(Mod[M // 2].values())) // 2
print(cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():

    return

#D
def D():
    n,m = LI()
    x = LI()
    d = defaultdict(lambda : 0)
    for i in x:
        d[i] += 1
    f = [[0]*2 for i in range(m)]
    for i,j in d.items():
        k = i%m
        f[k][0] += j-(j&1)
        f[k][1] += j&1
    ans = sum(f[0])>>1
    for i in range(1,(m>>1)+1):
        if i == m-i:
            ans += sum(f[i])>>1
            break
        a,b,c,d = f[i][0],f[i][1],f[m-i][0],f[m-i][1]
        if a+b <= c+d:
            ans += a+b
            if a+b <= d:
                ans += c>>1
            else:
                ans += (c-(a+b-d))>>1
        else:
            ans += c+d
            if c+d <= b:
                ans += a>>1
            else:
                ans += (a-(c+d-b))>>1
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
X = list(map(int, sys.stdin.readline().split()))
X = np.array(X)

ML = [[] for m in range(M)]
for x in X:
    ML[x % M].append(x)
counts = [[] for m in range(M)]
remains = [0] * M
even_sums = [0] * M
for m, li in enumerate(ML):
    counts[m] = list(Counter(li).values())
    remains[m] = len([c for c in counts[m] if c % 2 == 1])
    even_sums[m] = sum([c // 2 * 2 for c in counts[m]])

ans = 0
for m in range(M):
    m1 = m
    m2 = (M - m) % M

    if m1 == m2:
        rem = remains[m1] // 2
        remains[m1] -= rem * 2
        ans += rem
        if remains[m1]:
            rem = min(even_sums[m1] , remains[m1])
            remains[m1] -= rem
            even_sums[m2] -= rem
            ans += rem
    else:
        rem = min(remains[m1], remains[m2])
        remains[m1] -= rem
        remains[m2] -= rem
        ans += rem
        if remains[m1]:
            rem = min(even_sums[m2], remains[m1])
            remains[m1] -= rem
            even_sums[m2] -= rem
            ans += rem
        if remains[m2]:
            rem = min(even_sums[m1], remains[m2])
            remains[m2] -= rem
            even_sums[m1] -= rem
            ans += rem
for m in range(M):
    ans += even_sums[m] // 2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
N,M=map(int,input().split())
X=list(map(int,input().split()))
tab=[0]*M
cnts=[defaultdict(lambda: 0) for _ in range(M)]
for x in X:
    tab[x%M]+=1
    cnts[x%M][x]+=1
    
ans=0
for i in range(M//2+1):
    if i==0 or (M%2==0 and i==M//2):
        npair = tab[i]//2
        tab[i]-= 2*npair
        ans += npair
    else:
        npair = min(tab[i],tab[M-i])
        tab[i]-= npair
        tab[M-i]-= npair
        ans += npair

for remn, d in zip(tab, cnts):
    tmp=0
    for _,n in d.items():
        tmp += (n//2)
    ans += min(tmp, remn//2)

print(ans)

Submission status: Accepted

Solution code:
import collections
N, M = [int(_) for _ in input().split()]
X = [int(_) for _ in input().split()]
rlist = [[0, collections.defaultdict(int), 0] for _ in range(M)]
for x in X:
    rlist[x % M][0] += 1
    rlist[x % M][2] += 1
    rlist[x % M][1][x] += 1
ans = rlist[0][0] // 2
if M % 2 == 0:
    ans += rlist[M // 2][0] // 2
    rlist[M // 2][0] %= 2
for i in range(1, (M + 1) // 2):
    x = min(rlist[i][0], rlist[M - i][0])
    rlist[i][0] -= x
    rlist[M - i][0] -= x
    ans += x
for i in range(1, M):
    if rlist[i][0] and 2 * i != M:
        c = res = 0
        for k in rlist[i][1].values():
            res += k % 2
            c += k // 2
        cut = rlist[i][2] - rlist[i][0] - res
        cut += cut % 2
        cut //= 2
        cut = max(0, cut)
        ans += c - cut
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))

rem_memo = {}
rem_pair_memo = {}
cnt_memo = {}
for i in range(n):
    rem = x[i] % m
    if rem not in rem_memo:
        rem_memo[rem] = 1
    else:
        rem_memo[rem] += 1
        
    if x[i] not in cnt_memo:
        cnt_memo[x[i]] = 1
    else:
        cnt_memo[x[i]] += 1
        if cnt_memo[x[i]] % 2 == 0:
            if rem not in rem_pair_memo:
                rem_pair_memo[rem] = 1
            else:
                rem_pair_memo[rem] += 1

ans = 0
for i in rem_memo:
    if i == 0 or i == m-i:
        tmp = rem_memo[i] // 2
        ans += tmp
        rem_memo[i] -= tmp * 2
        continue
    if m-i in rem_memo:
        tmp = min(rem_memo[i], rem_memo[m-i])
        ans += tmp
        rem_memo[i] -= tmp
        rem_memo[m-i] -= tmp

for i in rem_memo:
    if i in rem_pair_memo:
        ans += min(rem_pair_memo[i], rem_memo[i] // 2)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
x = list(map(int, input().split()))
mods = [0 for _ in range(m)]
pairs = [0 for _ in range(m)]
c = Counter()
for y in x:
	mods[y%m] += 1
	c[y] += 1
	if c[y]%2 == 0:
		pairs[y%m] += 1
#print(mods, pairs)
ans = 0
ans += mods[0]//2
if m%2 == 0:
	ans += mods[m//2]//2
for i in range(1, (m+1)//2):
	mi = min(mods[i], mods[m-i])
	ans += mi
	mods[i] -= mi
	mods[m-i] -= mi

for i in range(m):
	if i == 0 or 2*i == m:
		continue
	else:
		ans += min(pairs[i], mods[i]//2)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))


Group = defaultdict(list)
keys = set()
for x in X:
    Group[x % M].append(x)
    keys.add(x % M)


ans = 0
for surplus in keys:
    s, t = Group[surplus], Group[M - surplus]
    s_size, t_size = len(s), len(t)
    # tの方が小さくなるようにswap
    if t_size > s_size:
        s, t = t, s
        s_size, t_size = len(s), len(t)
        surplus = M - surplus

    if (surplus == 0) or (surplus == M - surplus):
        ans += s_size // 2
    else:
        size_diff = s_size - t_size
        i = 0

        while i + 1 < s_size:
            if (s[i] == s[i + 1]) and (size_diff - 2 >= 0):
                size_diff -= 2
                ans += 1
                i += 1
            i += 1
        ans += t_size
    Group[surplus], Group[M - surplus] = [], []

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
n,m=map(int,input().split())
X=tuple(map(int,input().split()))
C=Counter(X)
Pairs=defaultdict(int)
Modcnt=defaultdict(int)
for k,v in C.items():
    Pairs[k%m]+=v//2
    Modcnt[k%m]+=v
ans=0
for i in range(m//2+1):
    if i==0 or i==m-i:
        ans+=Modcnt[i]//2
    else:
        if Modcnt[i]>=Modcnt[m-i]:
            k,l=i,m-i
        else:
            k,l=m-i,i
        a,b=Modcnt[k],Modcnt[l]
        ans+=b
        a-=b
        ans+=min(Pairs[k],a//2)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    modcnt = [0] * M
    pairs = [0] * M
    cnt = defaultdict(lambda: 0)
    for x in X:
        cnt[x] += 1
        key = x % M
        modcnt[key] += 1
        if cnt[x] % 2 == 0:
            pairs[key] += 1
    ans = modcnt[0] // 2
    for i in range(1, M//2+1):
        if i * 2 == M:
            ans += modcnt[i] // 2
        else:
            tmp = min(modcnt[i], modcnt[M-i])
            ans += tmp
            ans += min((modcnt[i] - tmp) // 2, pairs[i])
            ans += min((modcnt[M-i] - tmp) // 2, pairs[M-i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*X, = map(int,input().split())

cnt = [0]*(10**5+10)
cntMod = [0]*M
cntPairsMod = [0]*M
for x in X:
    cnt[x] +=1
    cntMod[x%M] +=1
for i,c in enumerate(cnt):
    cntPairsMod[i%M] += (c//2)*2

ans = cntMod[0]//2
if M%2==0:ans += cntMod[M//2]//2
for i in range(1,M//2 +M%2):
    j = M-i
    pairs = min(cntMod[i],cntMod[j])
    ans += pairs
    cntMod[i] -= pairs
    cntMod[j] -= pairs
    ans += min(cntMod[i],cntPairsMod[i])//2
    ans += min(cntMod[j],cntPairsMod[j])//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
X = list(map(int, input().split()))

# Mで割った余りに着目する
# 余りがiの整数は余りがM-iの整数とペアになれる
# 余りがiである整数のコレクションをA, M-iである整数のコレクションをBとする
# |A| > |B| ならば Aの要素同士で |A| = |B| または |B| + 1 となるまでペアを作る
# |A| < |B| ならば Bの要素同士で |B| = |A| または |A| + 1 となるまでペアを作る
# その後、A, B間でペアを作ればよい
Y = [defaultdict(int) for i in range(M)]
for x in X:
    Y[x % M][x] += 1
S = [sum(s for s in y.values()) for y in Y]
ans = S[0] // 2 + sum(
    S[M - i] + min(
        sum(v // 2 for v in Y[i].values()),
        (S[i] - S[M - i]) // 2
    ) if S[i] >= S[M - i] else
    S[i] + min(
        sum(v // 2 for v in Y[M - i].values()),
        (S[M - i] - S[i]) // 2
    )
    for i in range(1, (M + 1) // 2)
) + (
    S[M // 2] // 2 if M % 2 == 0 else
    0
)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n, m = [int(item) for item in input().split()]
x = [int(item) for item in input().split()]

modm = [[] for _ in range(m)]
ans = 0
for item in x:
    modm[item % m].append(item)
for i in range(m//2+1):
    if i == 0:
        ans += len(modm[i]) // 2
    elif m % 2 == 0 and i == m // 2:
        ans += len(modm[i]) // 2
    else:
        a = modm[i]
        b = modm[m - i]
        if len(b) < len(a):
            a, b = b[:], a[:]
        ans += len(a)
        cnt = Counter(b)
        val = 0
        for key in cnt.keys():
            val += cnt[key] // 2
        ans += min(val, (len(b) - len(a)) // 2)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+m%2):
  x,y=v[i],v[m-i]
  d=len(x)-len(y)
  if d<0:d,x,y=-d,y,x
  c=sorted([p[1] for p in Counter(x).items()])
  p=0
  for t in c:p+=t//2
  a+=len(y)+min(p,d//2)
a+=len(v[0])//2+(1-m%2)*len(v[m//2])//2
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+m%2):
  x,y=v[i],v[m-i]
  d=len(x)-len(y)
  if d<0:
    d=-d
    x,y=y,x
  c=sorted([p[1] for p in Counter(x).items()])
  p=0
  for t in c:
    p+=(t//2)
  a+=len(y)+min(p,(d//2))
a+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+1*(m%2==1)):
  x,y=v[i],v[m-i]
  d=len(x)-len(y)
  if d<0:
    d=-d
    x,y=y,x
  c=sorted(Counter(x).items(),key=lambda x:x[1])
  p=0
  for t in c:
    p+=(t[1]//2)
  a+=len(y)+min(p,(d//2))
a+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+1*(m%2==1)):
  d=len(v[i])-len(v[m-i])
  if d<0:
    d=-d
    v[i],v[m-i]=v[m-i],v[i]
  c=sorted(Counter(v[i]).items(),key=lambda x:x[1])
  p=0
  for t in c:
    p+=(t[1]//2)
  a+=len(v[m-i])+min(p,(d//2))
a+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:
    v[i%m].append(i)
ans=0
for i in range(1,m//2+1*(m%2==1)):
    d=len(v[i])-len(v[m-i])
    if d<0:
        d=-d
        v[i],v[m-i]=v[m-i],v[i]
    c=sorted(Counter(v[i]).items(),key=lambda x:x[1])
    p=0
    for t in c:
        p+=(t[1]//2)
    ans+=len(v[m-i])+min(p,(d//2))

ans+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter


N, M = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
c = Counter(x)
a = defaultdict(int)
E = defaultdict(int)
for i,j in c.items():
    a[i%M] += j
    E[i%M] += j//2
ans = a[0]//2
for i in range(1, M):
    j = M - i
    if i < j:
        m = min(a[i], a[j])
        t = min((a[i] - m)//2, E[i]) + min((a[j] - m)//2, E[j])
        ans += m+t
    elif i == j: #i==0は最初のifにかかってしまうため注意
        ans += a[i] //2

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
xlist = list(sorted(map(int, input().split())))
xd = {}

modl = [0 for _ in range(m)]
for x in xlist:
  modl[x%m] += 1
  if x in xd:
    xd[x] += 1
  else:
    xd[x] = 1

mina = modl[0] // 2
ans = mina
modl[0] -= mina*2
for i in range(1, m//2+1):
  if i != m-i:
    mina = min(modl[i], modl[m-i])
    ans += mina
    modl[i] -= mina
    modl[m-i] -= mina
  else:
    mina = modl[i] // 2
    ans += mina
    modl[i] -= mina*2

for k, v in xd.items():
  tmp = min(v//2, modl[k%m]//2)
  ans += tmp
  modl[k%m] -= tmp * 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
def inpl(): return list(map(int, input().split()))

N, M = inpl()
X = sorted(inpl())
C = Counter(X)
D = defaultdict(int)
E = defaultdict(int)
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
N,m=map(int,input().split())

X=list(map(int,input().split()))

#print(X)

M=[[]for i in range(m)]
for i in range(len(X)):
    M[X[i]%m].append(X[i])
    
#print(M)

ans=len(M[0])//2
if m%2==0:
    ans+=len(M[m//2])//2
#print(0,ans)
for i in range(1,(m//2)+1):
    if m%2==0:
        if i==(m//2):
            break
    ans+=min(len(M[i]),len(M[m-i]))
    #print(i,ans)
    L=[0]
    cnt=1
    if len(M[i])>len(M[m-i]):
        A=M[i]
    else:
        A=M[m-i]
    A.sort()
    for j in range(1,max(len(M[i]),len(M[m-i]))):
        if A[j]==A[j-1]:
            cnt+=1
        else:
            L.append(cnt//2)
            cnt=1
    L.append(cnt//2)
    #print(L)
    if (abs(len(M[i])-len(M[m-i]))//2)<=sum(L):
        ans+=(abs(len(M[i])-len(M[m-i]))//2)
    else:
        ans+=sum(L)
    #print(i,ans)
print(ans)