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:
from collections import Counter, defaultdict
N, M, *X = map(int, open(0).read().split())
c = Counter(X)
dic = defaultdict(int)
nokori = defaultdict(int)
ans = 0
for k in c.keys():
  dic[k%M] += c[k]//2
  nokori[k%M] += c[k]%2
ans = 0
for a in range(M//2+1):
  b = (M-a)%M
  na = nokori[a]
  nb = nokori[b]
  if a==b:
    ans += na//2
    ans += dic[a]
    continue
  if na<nb:
    ans += na
    nb -= na
    ma = dic[a]*2
    ans += min(nb,ma)
    ans += max(0,(ma-nb)//2)
    ans += dic[b]
  else:
    ans += nb
    na -= nb
    mb = dic[b]*2
    ans += min(mb,na)
    ans += max(0,(mb-na)//2)
    ans += dic[a]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
X = LI()
D = defaultdict(lambda:defaultdict(int))
for k in X:
    D[k % m][k] += 1

ans = 0
if m % 2 == 0:
    ans += sum(D[m // 2].values()) // 2

ans += sum(D[0].values()) // 2

for i in range(1, (m + 1) // 2):
    x = D[i].values()
    y = D[m - i].values()
    if sum(x) > sum(y):
        x, y = y, x
    x_sum = sum(x)
    y_sum = sum(y)
    ans += x_sum
    ret = 0
    for j in y:
        ret += j // 2 * 2
        if ret > y_sum - x_sum:
            ans += (y_sum - x_sum) // 2
            break
    else:
        ans += ret // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

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

cntMod = defaultdict(int)
cntDup = defaultdict(int)

for x, c in Counter(X).items():
    cntMod[x % M] += c
    cntDup[x % M] += c // 2

ans = 0
for m in range(M):
    if m > M // 2:
        break
    n = (M - m) % M

    if n == m:
        ans += cntMod[n] // 2
    else:
        mi = min(cntMod[n], cntMod[m])
        ans += mi
        cntMod[n] -= mi
        cntMod[m] -= mi
        ans += min(cntMod[n] // 2, cntDup[n])
        ans += min(cntMod[m] // 2, cntDup[m])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mx = a[-1]
table = [[] for _ in range(M)]
ctable = [0] * (mx + 1)
for x in a: ctable[x] += 1
for x in a:
  if ctable[x] % 2:
    ctable[x] -= 1
    table[x % M].append(x)
for i in range(mx + 1):
  table[i % M] += [i] * ctable[i]

for i in range(M): table[i].reverse()
#print(table)

res = 0
for x in range(M):
  y = (M - x) % M
  if x != y:
    while len(table[x]) > 0 and (len(table[y]) > 0):
      res += 1
      table[x].pop()
      table[y].pop()
  else:
    while len(table[x]) // 2 > 0:
      res += 1
      table[x].pop()
      table[x].pop()

ctable = [0] * (mx + 1)
for i in range(M):
  for x in table[i]:
    ctable[x] += 1
for i in range(mx + 1): res += ctable[i] // 2
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
from collections import Counter
mo=[[]for _ in range(m)]
for i in a:mo[i%m].append(i)
ans=len(mo[0])//2
if m%2==0:ans+=len(mo[m//2])//2
for i in range(1,0--m//2):
  if len(mo[i])>len(mo[m-i]):d=Counter(mo[i])
  elif len(mo[i])==len(mo[m-i]):
    ans+=len(mo[i])
    continue
  else:d=Counter(mo[m-i])
  anss=0
  for j in d:anss+=d[j]//2
  ans+=min(len(mo[i]),len(mo[m-i]))+min(abs(len(mo[i])-len(mo[m-i]))//2,anss)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
uni, dup = [0]*M, [0]*M
for k, v in Counter(map(int, input().split())).items():
    uni[k % M] += v % 2
    dup[k % M] += v - (v & 1)

ans = (uni[0] + dup[0]) // 2

for i in range(1, (M+1)//2):
    x = min(uni[i], uni[M-i])
    y = min(uni[i]-x, dup[M-i])
    z = min(uni[M-i]-x, dup[i])
    ans += x + y + z + (dup[M-i]-y)//2 + (dup[i]-z)//2

if M % 2 == 0:
    ans += (uni[M//2] + dup[M//2]) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

pair = [[] for _ in range(M)]
for x in X:
    mod = x % M
    pair[mod].append(x)

ans = 0

# 余りが0の組
ans += len(pair[0]) // 2
if M % 2 == 0:
    ans += len(pair[M // 2]) // 2

for i in range(1, M):
    j = M - i
    if i >= j:
        break
    S = pair[i]
    T = pair[j]
    if len(S) < len(T):
        S = pair[j]
        T = pair[i]

    c = Counter(S)
    p = 0
    r = 0
    for v in c.values():
        div, mod = divmod(v, 2)
        r += mod
        p += div * 2

    add = len(T)
    ans += add
    add -= min(add, r)
    ans += (p - add) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(Xs)

nums = [0] * M
numSames = [0] * M
for key, num in cnt.items():
    k = key%M
    nums[k] += num
    numSames[k] += num//2

ans = 0
for k in range(M//2+1):
    k2 = M-k
    if k == 0 or k == k2:
        numPair = nums[k]//2
        ans += numPair
        nums[k] -= numPair*2
    else:
        numPair = min(nums[k], nums[k2])
        ans += numPair
        nums[k] -= numPair
        nums[k2] -= numPair

for k in range(M):
    ans += min(numSames[k], nums[k]//2)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
X = lr()
remain = [[] for _ in range(M)]
for x in X:
    remain[x%M].append(x)

num = [0] * M
for i in range(M):
    num[i] = len(remain[i])

answer = 0
for i in range(M//2 + 1):
    if i == 0:
        answer += num[0] // 2
        num[0] %= 2
    elif i == (M-i):
        answer += num[i] // 2
        num[i] %= 2
    else:
        x = min(num[i], num[M-i])
        answer += x
        num[i] -= x; num[M-i] -= x

for i in range(M):
    counter = Counter(remain[i])
    pair = 0
    for v in counter.values():
        pair += v//2
    answer += min(pair, num[i] // 2)

print(answer)
# 17

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

x.sort()

#p : 同じやつの組が何ペア
p = [0]*m
# mod M 何個
q = [0]*m

cnt = 1
for i in range(n):
    q[x[i]%m] += 1
    if i == n-1 or x[i] != x[i+1]:
        p[x[i]%m] += cnt//2
        cnt = 1
    else:
        cnt += 1

res = 0

for i in range(m):
    if i==0:
        res += q[0]//2
        continue
    if i > m-i:
        break
    if i == m-i:
        res += q[i]//2
        continue

    if q[i] >= q[m-i]:
        res += q[m-i]
        q[i] -= q[m-i]
        res += min(q[i]//2,p[i])
    else:
        res += q[i]
        q[m-i] -= q[i]
        res += min(q[m-i]//2,p[m-i])
print(res)

Submission status: Accepted

Solution code:
n,m,*X=map(int,open(0).read().split())
E=[0]*(max(X)+1)
P=[0]*m
M=[0]*m
for x in X:E[x]+=1;M[x%m]+=1
for i,e in enumerate(E):P[i%m]+=e//2
ans=0
min=lambda a,b: a if a<b else b
for i in range(m//2+1):
	if i==0 or i*2==m:
		ans+=M[i]//2
	else:
		l=min(M[i],M[(m-i)%m])
		ans+=l+min((M[i]-l)//2,P[i])+min((M[(m-i)%m]-l)//2,P[(m-i)%m])
print(ans)

Submission status: Accepted

Solution code:
n,m,*X=map(int,open(0).read().split())
E=[0]*(max(X)+1)
P=[0]*m
M=[0]*m
for x in X:E[x]+=1;M[x%m]+=1
for i,e in enumerate(E):P[i%m]+=e//2
ans=0
for i in range(m//2+1):
	if i==0 or i*2==m:
		ans+=M[i]//2
	else:
		l=min(M[i],M[(m-i)%m])
		ans+=l+min((M[i]-l)//2,P[i])+min((M[(m-i)%m]-l)//2,P[(m-i)%m])
print(ans)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    x = list(map(int,input().split()))
    
    ml = [[] for _ in range(M)]
    for num in x:
        ml[num%M].append(num)

    cl = [[0,0] for _ in range(M)]
    for i in range(M):
        y = ml[i]
        c = tuple(Counter(y).values())
        for num in c:
            cl[i][0] += num//2*2
            cl[i][1] += num%2

    ans = (cl[0][0]+cl[0][1])//2
    for i in range(1,-(-M//2)):
        da,oa = cl[i]
        db,ob = cl[M-i]
        num = 0
        if oa >= ob:
            num += (ob+min(oa-ob,db)+max(0,db-(oa-ob))//2+da//2)
        else:
            num += (oa+min(ob-oa,da)+max(0,da-(ob-oa))//2+db//2)
        ans += num
    
    if M%2 == 0:
        m = M//2
        ans += (cl[m][0]+cl[m][1])//2
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
x = list(map(int, input().split()))
c = [0] * m
for y in x:
    c[y % m] += 1
ans = c[0] // 2
c[0] = 0
for i in range((m - 1) // 2):
    t = min(c[i + 1], c[m - i - 1])
    ans += t
    c[i + 1] -= t
    c[m - i - 1] -= t
if m % 2 == 0:
    ans += c[m // 2] // 2
    c[m // 2] %= 2
c2 = Counter(x)
for k, v in c2.items():
    ans += min(c[k % m], v) // 2
    c[k % m] -= min(c[k % m], v) // 2 * 2
print(ans)

Submission status: Accepted

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

table = collections.defaultdict(list)
for x in X:
    table[x % M].append(x)
Count = [None]*M
for i in range(M):
    Count[i] = collections.Counter(table[i]).values()
ans = 0
for i in range(M // 2 + 1):
    tmp = min(len(table[i]), len(table[(M-i) % M]))
    if i != (M-i) % M:
        ans += tmp
    else:
        ans += tmp // 2

    k = 0
    l = 0
    for x in Count[i]:
        k += x % 2
        l += x // 2
    if tmp <= k:
        ans += l
    else:
        ans += ((k + l*2) - tmp) // 2

    if i != (M-i) % M:
        k = 0
        l = 0
        for x in Count[(M-i) % M]:
            k += x % 2
            l += x // 2
        if tmp <= k:
            ans += l
        else:
            ans += ((k + l*2) - tmp) // 2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
m = [0] * M
d = [0] * (max(a) + 1)
for x in a:
  d[x] += 1
  m[x % M] += 1

res = 0
for i in range(M):
  t = min(m[i], m[(M - i) % M])
  if i == (M - i) % M:
    t = m[i] // 2
  m[i] -= t
  m[(M - i) % M] -= t
  res += t

for i in range(N):
  x = a[i]
  if m[x % M] > 1:
    k = m[x % M] // 2
    if d[x] > 1:
      t = min(d[x] // 2, k)
      res += t
      d[x] -= t * 2
      m[x % M] -= t * 2
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n,m = getlist()
    nums = getlist()

    cnt = Counter(nums)
    mod = [0 for i in range(m)]
    same = [0 for i in range(m)]

    for k, v in cnt.items():
        mod[k%m] += v
        same[k%m] += v // 2

    ans = mod[0] // 2
    for i in range(1, int((m+2) // 2)):
        if i == m / 2:
            ans += mod[i] // 2
        else:
            other = m - i
            ans += min(mod[i], mod[other])
            if mod[i] > mod[other]:
                ans += min(same[i], (mod[i] - mod[other]) // 2)
            if mod[i] < mod[other]:
                ans += min(same[other], -(mod[i] - mod[other]) // 2)

    print(ans)

    # print(same, mod)

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
X = list(map(int, input().split()))
R = [0]*M
R_paired = [0]*M
d = defaultdict(int)
for x in X:
    d[x]+=1
for k, v in d.items():
    if v%2 == 1:
        R[k%M]+=1
        R_paired[k%M]+=v//2
    else:
        R_paired[k%M]+=v//2
ans = R[0]//2
for i in range(1, (M-1)//2+1):
    if R[i]>R[M-i]:
        if R_paired[M-i]:
            r = min(R_paired[M-i], (R[i]-R[M-i])//2)
            R_paired[M-i]-=r
            R[M-i]+=2*r
    else:
        if R_paired[i]:
            r = min(R_paired[i], (R[M-i]-R[i])//2)
            R_paired[i]-=r
            R[i]+=2*r
    ans+=min(R[i], R[M-i])
if M%2 == 0:
    ans+=R[M//2]//2
ans+=sum(R_paired)
print(ans)

Submission status: Accepted

Solution code:
#12:26
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
same = []
b = []
for i in range(1,n):
  if a[i-1] == a[i]:
    same.append(a[i])
    ans += 1
    a[i-1] = 0
    a[i] = 0
for i in range(n):
  if a[i] != 0:
    b.append(a[i])
#print(same,ans,b)
p = [0 for _ in range(k)]
q = [0 for _ in range(k)]
r = [0 for _ in range(k)]
for x in same:
  p[x%k] += 2
for x in b:
  q[-(x%k)] += 1
  r[x%k] += 1
#print(p)
#print(q)
#print(r)
#print(ans)
for i in range(k):
  if i*2 % k == 0:
    mini = min(q[i],r[i]) // 2
  else:
    mini = min(q[i],r[i])
  q[i] -= mini
  r[i] -= mini
  q[-i] -= mini
  r[-i] -= mini
  ans += mini
#print(p)
#print(q)
#print(r)
#print(ans)
for i in range(k):
  mini = min(p[i],q[i]) // 2
  if mini > 0:
    ans += mini
print(ans)

Submission status: Accepted

Solution code:

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

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

dic = {}

for i in X:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

lis = [0] * M
rem = [0] * M

for i in dic:

    lis[i % M] += dic[i]
    rem[i % M] += dic[i] // 2 * 2

#print (lis,rem)

ans = 0
for i in range((M-1) // 2):

    i += 1

    if lis[i] >= lis[-1*i]:
        ans += lis[-1*i] * 2 + min(rem[i] , (lis[i]-lis[-1*i]) // 2 * 2)

    else:
        ans += lis[i] * 2 + min(rem[-1*i] , (lis[-1*i] - lis[i]) // 2 * 2)

ans += lis[0] // 2 * 2

if M % 2 == 0:
    ans += lis[M//2] // 2 * 2
    

print (ans // 2)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m = inpm()
    x = inpl()
    x.sort()
    ans = 0
    y = [0 for _ in range(n)]
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    for i in range(n):
        y[i] = x[i]%m
        dic[y[i]] += 1
        dic2[x[i]] += 1
    for e in dic2:
        if dic2[e]>1:
            dic3[e%m] += dic2[e]//2
    for i in range(m):
        if i > m-i:
            break
        elif i == 0:
            ans += dic[i]//2
        elif i == m/2:
            ans += dic[i]//2
        else:
            ans += min(dic[i],dic[m-i])
            if dic[i] == dic[m-i]:
                continue
            elif dic[i] > dic[m-i]:
                a = (min(dic[i]-dic[m-i],dic3[i]*2))//2
                if a>0:
                    ans += a
            elif dic[i] < dic[m-i]:
                a = (min(dic[m-i]-dic[i],dic3[m-i]*2))//2
                if a>0:
                    ans += a
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    X=LI()
    d = defaultdict(int)
    double = defaultdict(int)
    for x in X:
        d[x%M] += 1
        double[x] += 1
    ans = 0
    for x in X:
        x = x%M
        if d[x]>=1 and d[(M-x)%M]>=1:
            if x==(M-x)%M and d[x]<2:
                continue
            ans += 1
            d[x]-=1
            d[(M-x)%M]-=1
    for x in X:
        ori_x = x
        x = x%M
        if double[ori_x]>=2 and d[x]>=2:
            ans += 1
            d[x]-=2
            double[ori_x]-=2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
Y = list(map(int,input().split()))

l = max(Y) + 1
X = [0] * l
for i in range(n):
    X[Y[i]] += 1

# print(X)
U = [[0] * m for i in range(2)]

for i in range(l):
    a = X[i] // 2
    U[0][i % m] += a

A = [0] * m
for i in range(l):
    A[i % m] += X[i]
# print(A)

for i in range(1, m//2 + 1):
    a = min(A[i], A[m-i])
    U[1][i] += a
    U[1][m-i] += a

U[1][0] = A[0]

# print(U)

ans = 0
for i in range(m):
    ans += min((A[i]-U[1][i]) // 2, U[0][i]) * 2 + U[1][i]

print(ans // 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    x = LI()
    d = defaultdict(int)
    l = [defaultdict(int) for _ in range(m)]
    for a in x: d[a % m] += 1; l[a % m][a] += 1
    ans = 0
    for a in range((m >> 1) + 1):
        if a == m - a or a == 0:
            ans += d[a] >> 1
        else:
            tmp = min(d[a], d[m - a])
            ans += tmp
            if d[a] < d[m - a]:
                tmp = d[m - a] - d[a]
                for value in l[m - a].values():
                    if tmp < 2:
                        break
                    if value >> 1:
                        t = min(tmp >> 1, value >> 1)
                        ans += t
                        tmp -= 2 * t
            else:
                tmp = d[a] - d[m - a]
                for value in l[a].values():
                    if tmp < 2:
                        break
                    if value >> 1:
                        t = min(tmp >> 1, value >> 1)
                        ans += t
                        tmp -= 2 * t
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter
n,m = map(int, input().split())
a = list(map(int, input().split()))
amax = max(a)
c = [0]*(amax+1)
b = [a[i]%m for i in range(n)]
rem = [0]*m
for i in range(n):
    rem[b[i]] += 1
    c[a[i]] += 1
ans = 0
for i in range(m//2+1):
    if i == 0 or i*2 == m:
        ans += rem[i]//2
        rem[i] -= rem[i]//2*2
        continue
    less = min(rem[i],rem[m-i])
    ans += less
    rem[i] -= less
    rem[m-i] -= less
for j in range(amax//m+1):
    for i in range(m):
        if m*j+i<=amax:
            if rem[i] >= c[m*j+i]:
                ans += c[m*j+i]//2
                rem[i] -= c[m*j+i]//2*2
            else:
                ans += rem[i]//2
                rem[i] -= rem[i]//2*2
print(ans)

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

def solve():
    n,m = LI()
    x = LI()
    d = [[0]*2 for i in range(m)]
    for i in x:
        d[i%m][0] += 1
    x.sort()
    for i in range(max(x)+1):
        k = bisect.bisect_right(x,i)-bisect.bisect_left(x,i)
        if k > 1:
            p = i%m
            s = k >> 1
            d[p][0] -= 2*s
            d[p][1] += 2*s
    ans = 0
    for i in range(1,((m+1)>>1)):
        a,b = d[i]
        c,d_ = d[m-i]
        if a+b > c+d_:
            a,c = c,a
            b,d_ = d_,b
        ans += a+b
        if a+b <= c:
            c -= a+b
            ans += d_ >> 1
        else:
            d_ -= (a+b-c)
            ans += d_ >> 1
    ans += sum(d[0])>>1
    if not m&1:
        k = m >> 1
        ans += sum(d[k])>>1
    print(ans)
    return

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

Submission status: Accepted

Solution code:
def examA():
    H, W = LI()
    S = [LSI() for _ in range(H)]
    Alpha = [chr(ord('A') + i) for i in range(26)]
    for i in range(H):
        for j in range(W):
            if S[i][j]=="snuke":
                ans = str(Alpha[j]) + str(i+1)
    print(ans)
    return

def examB():
    N = I()
    ans = []
    cur = int((N*2-1)**0.5)+1
    ansC = (cur+1)*cur//2
    neg = ansC-N
    if neg>cur:
        cur -=1
        ansC = (cur + 1) * cur // 2
        neg = ansC - N
    for i in range(1,cur+1):
        if i!=neg:
            ans.append(i)
    for v in ans:
        print(v)
#    print(cur,neg)
    return

def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    que = deque()
    que.append(e)
    len = [10**9]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowlen = len[now]
        for ne in fordfs[now]:
            if len[ne] == 10**9:
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examC():
    N, M = LI()
    V = [[]for _ in range(N+M)]
    for i in range(N):
        L = LI()
        for k in range(1,L[0]+1):
            V[i].append(L[k]+N-1)
            V[L[k]+N-1].append(i)
    length = bfs(N+M,0,V)
    ans = "YES"
    for i in length[:N]:
        if i==10**9:
            ans = "NO"
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); maxX = max(X)+1
    dx = defaultdict(int)
    dm = [set()for _ in range(M)]
    d = defaultdict(int)
    for x in X:
        dx[x] +=1
        d[x%M] +=1
        dm[x%M].add(x)
    ans = 0
#    print(d); print(dx); print(dm)
    ans +=d[0]//2
    d[0] = 0
    for i in range(1,1+M//2):
        cur = min(d[i],d[M-i])
        ans +=cur
        d[i] -=cur; d[M-i] -=cur
#    print(ans); print(d)
    for i in d.keys():
        for j in dm[i]:
            cur = min(dx[j]//2,d[i]//2)
            d[i] -= cur * 2
            ans += cur
            if d[i]<=1:
                break
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Accepted

Solution code:
from collections import Counter as c
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=c(a)
d=[0]*m
e=[0]*m
for i in b.keys():
    t=b[i]
    d[i%m]+=t
    e[i%m]+=t//2
z=0
for i in range(1,(m+1)//2):
    x,y=d[i],d[-i]
    if x>y:
        z+=d[-i]+min(e[i],(d[i]-d[-i])//2)
    else:
        z+=d[i]+min(e[-i],(d[-i]-d[i])//2)
if m%2==0:
    z+=d[m//2]//2
z+=d[0]//2
print(z)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = list(map(int, input().split()))
n_ = max(g)+1
l = [False]*n_
p = [0]*m
b = [0]*m
for x in g:
  b[x%m] += 1
  if l[x]:
    p[x%m] += 2
    l[x] = False
  else:
    l[x] = True
ans = b[0]//2
for i in range(1,(m+1)//2):
  cur = min(b[i],b[m-i])
  ans += cur
  ans += min(b[i]-cur, p[i])//2
  ans += min(b[m-i]-cur,p[m-i])//2
if not m%2:
  ans += b[m//2]//2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X):
    D = defaultdict(list)
    for x in X:
        D[x%M].append(x)
    ans = 0
    for i in range(1, M//2+1):
        j = M - i
        if i == j:
            continue
        if len(D[i]) == len(D[j]):
            ans += len(D[i])
        else:
            l = D[i]
            s = D[j]
            if len(l) < len(s):
                l, s = s, l
            C = list(Counter(l).values())
            h = []
            for c in C:
                if c % 2 == 1:
                    h.append(1)
                    c -= 1
                if c != 0:
                    h.append(c)
            heapq.heapify(h)
            s = len(s)
            while h and s > 0:
                c = heapq.heappop(h)
                if c == 1:
                    ans +=1
                    s -= 1
                else:
                    if s >= c:
                        ans += c
                        s -= c
                    else:
                        ans += s
                        heapq.heappush(h, c-s)
                        s = 0
            while h:
                c = heapq.heappop(h)
                ans += c // 2
    ans += len(D[0]) // 2
    if M % 2 == 0:
        ans += len(D[M//2]) // 2
    return ans


def main():
    N, M = read_int_n()
    X = read_int_n()
    print(slv(N, M, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#違う数との組-->同じ数での組の順に考える

from collections import defaultdict, Counter

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

d = defaultdict(int) #mod Mで見たときの個数
for x in X:
    d[x % M] += 1


ans = 0 #Mの倍数//2 組の和はすべてMの倍数となる

lst = [0] * M
for m in range(1, M):
    ans += min(d[m], d[M - m])
    lst[m] = d[m] - min(d[m], d[M - m]) #mod Mで見たときに残っている個数

ans //= 2

ans += d[0] // 2 #0だけは1ダブルカウントしていないのであとから足す

C = Counter(X)
for c in C:
    tmp = min(C[c], lst[c % M]) // 2
    lst[c % M] -= 2 * tmp
    ans += tmp

print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter

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

d = defaultdict(int) #mod Mで見たときの個数
for x in X:
    d[x % M] += 1


ans = 0 #Mの倍数//2 組の和はすべてMの倍数となる
# ans += d[0] // 2

lst = [0] * M
for m in range(1, M):
    ans += min(d[m], d[M - m])
    lst[m] = d[m] - min(d[m], d[M - m]) #mod Mで見たときに残っている個数

ans //= 2
ans += d[0] // 2
# print (ans)
# print ('lst', lst)
# print ('d', d)

C = Counter(X)
for c in C:
    tmp = min(C[c], lst[c % M]) // 2
    lst[c % M] -= 2 * tmp
    ans += tmp

print (ans)