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:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(x))
  cxmod=dict(Counter(xmod))
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod=Counter(xmod)
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()

Submission status: Accepted

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

from collections import Counter
cs = [Counter() for _ in range(M+1)]
ca = Counter()
for x in X:
    cs[x%M][x] += 1
    ca[x%M] += 1

ans = ca[0]//2
for i in range(1,(M+1)//2):
    j = M-i
    ans += min(ca[i], ca[j])
    if ca[i] > ca[j]:
        d = (ca[i] - ca[j]) // 2
        for v in cs[i].values():
            t = min(d, v//2)
            d -= t
            ans += t
            if d==0: break
    elif ca[i] < ca[j]:
        d = (ca[j] - ca[i]) // 2
        for v in cs[j].values():
            t = min(d, v//2)
            d -= t
            ans += t
            if d==0: break
if M%2==0:
    ans += ca[M//2]//2
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
a=[]
for i in range(m):
  a.append([])
for i in range(n):
  a[x[i]%m].append(x[i])
for i in range(m):
  a[i].sort()
ans=0
for i in range(1,(m+1)//2):
  if len(a[i])<len(a[m-i]):
    t=m-i
  else:
    t=i
  pairs=0
  r=0
  count=1
  for j in range(len(a[t])):
    if a[t][j]==r:
      count+=1
    else:
      pairs+=count//2
      count=1
      r=a[t][j]
  pairs+=count//2
  ans+=len(a[m-t])
  ans+=min((len(a[t])-len(a[m-t]))//2,pairs)
if m%2==0:
  ans+=len(a[m//2])//2
ans+=len(a[0])//2
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,m = readints()
x = readints()
modx = [i%m for i in x]

a = [0]*(10**5+1)
b = [0]*m
for i in range(n):
    a[x[i]]+=1
    b[modx[i]]+=1

ans = b[0]//2
b[0] = 0
y = m//2
if m%2==0:
    ans += b[m//2]//2
    b[m//2] = 0
else:
    y += 1
for i in range(1,y):
    c = min(b[i],b[m-i])
    b[i] -= c
    b[m-i] -= c
    ans += c
for i in range(10**5+1):
    if b[i%m]>1 and a[i]>1:
        c = min(b[i%m],a[i])//2
        ans += c
        b[i%m] -= c*2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M = map(int,input().split())
X = sorted(map(int,input().split()))
d = defaultdict(list)
for x in X:
    d[x%M].append(x)

res = 0
for i in range(M//2+1):
    j = (-i)%M

    if i == j:
        res += len(d[i])//2
    else:
        l, r = d[i], d[j]
        if len(l) < len(r):
            l,r = r,l

        t = 0
        last = None
        for v in l:
            if last is None:
                last = v
            elif last == v:
                t += 1
                last = None
            else:
                last = v

        res += len(r) + min((len(l)-len(r))//2, t)

print(res)

Submission status: Accepted

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

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

counter = Counter(Xs)
same_number_pairs = [0] * M #classify the number by (% M)
not_paired_numbers = [0] * M

for value, count in counter.items():
    same_number_pairs[value % M] += count // 2
    not_paired_numbers[value % M] += count % 2

sum_pairs = not_paired_numbers[0] // 2
not_paired_numbers[0] %= 2
if M % 2 == 0:
    sum_pairs += not_paired_numbers[M//2] // 2
    not_paired_numbers[M//2] %= 2
for i in range(1, (M+1)//2):
    pair = min(not_paired_numbers[i], not_paired_numbers[-i])
    sum_pairs += pair
    not_paired_numbers[i] -= pair
    not_paired_numbers[-i] -= pair

for mod, count in enumerate(not_paired_numbers):
    while same_number_pairs[(-mod)%M] >= 1 and count >= 2:
        same_number_pairs[(-mod)%M] -= 1
        count -= 2
        sum_pairs += 2

print(sum(same_number_pairs) + sum_pairs)

Submission status: Accepted

Solution code:
from collections import Counter

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

G = [0] * M
pairs_num = [0] * M
for k, v in ct.items():
    G[k % M] += v
    pairs_num[k % M] += v // 2

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

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
X = [int(x) for x in input().split()]

num = [0]*(max(X)+1)
R = [0]*M
for x in X:
    num[x] += 1
    R[x%M] += 1

ans = R[0]//2
for i in range(1, M//2+1):
    ans += min(R[i], R[M-i])
if M%2 == 0:
    ans -= R[M//2]-R[M//2]//2

for i in range(len(num)):
    if num[i] < 2 or i%M == 0:
        continue
    d = R[i%M]-R[M-i%M]
    if d < 2:
        continue
    t = min(d, num[i])//2
    ans += t
    R[i%M] -= 2*t

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
X=list(map(int,input().split()))
X.sort()
L=[[] for i in range(M)]
for i in range(N):
  L[X[i]%M].append(X[i])
for i in range(1,(M+1)//2):
  if len(L[i])<len(L[M-i]):
    L[i],L[M-i]=L[M-i],L[i]
P=0
X=0
B=0
for i in range(1,(M+1)//2):
  X=len(L[i])
  B=True
  for j in range(X-1):
    if B:
      if L[i][j]==L[i][j+1] and X-2>=len(L[M-i]):
        X-=2
        P+=1
        B=False
    else:
      B=True
  P+=min(X,len(L[M-i]))
P+=len(L[0])//2
if M&1==0:
  P+=len(L[M//2])//2
print(P)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(x)
cc = defaultdict(list)
onum = defaultdict(int)
esum = defaultdict(int)
for k,v in c.items():
    cc[k%m].append(v)
    if v%2:
        onum[k%m] += 1
        esum[k%m] += v-1
    else:
        esum[k%m] += v
    
def sub(l, o):
    return sum(item//2 for item in l) + o//2
def sub2(l1, o1, l2, o2, e1, e2):
    if o1==o2:
        return sum(item//2 for item in l1) + sum(item//2 for item in l2) + o1
    elif o1<o2:
        o1, o2 = o2, o1
        l1, l2 = l2, l1
        e1, e2 = e2, e1
    ans = 0
    ans += o2
    o1 = o1 - o2
    if o1 <= e2:
        ans += o1
        e2 -= o1
        ans += (e1//2) + (e2//2)
    else:
        ans += e2
        ans += (e1//2)
    return ans

if m%2==0:
    ans = 0
    ans += sub(cc[0], onum[0])
    ans += sub(cc[m//2], onum[m//2])
    for k in range(1,m//2):
        ans += sub2(cc[k], onum[k], cc[m-k], onum[m-k], esum[k], esum[m-k])
else:
    ans = 0
    ans += sub(cc[0], onum[0])
    for k in range(1,m//2+1):
        ans += sub2(cc[k], onum[k], cc[m-k], onum[m-k], esum[k],  esum[m-k])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
x = inl()
h = defaultdict(int)
for y in x:
    h[y] += 1
od = [0]*m
ev = [0]*m
for y in h:
    od[y%m] += h[y]%2
    ev[y%m] += h[y]-h[y]%2
ans = (ev[0]+od[0])//2
if m%2==0:
    ans += (ev[m//2]+od[m//2])//2
for i in range(1,m//2+m%2):
    a = od[i]
    b = ev[i]
    c = od[m-i]
    d = ev[m-i]
    if a>c+d:
        ans += c+d+b//2
    elif c>a+b:
        ans += a+b+d//2
    else:
        ans += (a+b+c+d)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
num = defaultdict(list)
ans = 0
for x in X:
  y = x % M
  num[y].append(x)
  pair = (M - y) % M
  if d[pair] >= 1:
    d[pair] -= 1
    ans += 1
  else:
    d[y] += 1

def count_pair(Z, n):
  res = 0
  dd = defaultdict(int)
  for z in Z:
    if dd[z] >= 1:
      res += 1
      dd[z] -= 1
    else:
      dd[z] += 1
  return min(res, n)

for y in num:
  ans += count_pair(num[y], d[y]//2)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n,m = map(int, input().split())
x = list(map(int, input().split()))
mod_count = [0] * m
pair = [0] * m
count = Counter(x)

for i in x:
  mod_count[i%m] += 1
for k,v in count.items():
  pair[k%m] += v // 2
ans = mod_count[0] // 2
if m % 2 == 0:
  ans += mod_count[m//2] // 2
for i in range(1,(m+1)//2):
  a1,a2 = mod_count[i], pair[i]
  b1,b2 = mod_count[m-i], pair[m-i]
  if a1 > b1:
    if a1 - a2 * 2 >= b1:
      ans += a2 + b1
    else:
      ans += (a1 + b1) // 2
  else:
    if b1 - b2 * 2 >= a1:
      ans += b2 + a1
    else:
      ans += (a1+b1) // 2
print(ans)

Submission status: Accepted

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

# if m == 1:
#     print(n//2)
#     exit()

lst = [{} for i in range(m)]
lst_num = [0 for i in range(m)]
for i in range(n):
    xi = x[i]
    amari = xi % m
    if xi in lst[amari]:
        lst[amari][xi] += 1
    else:
        lst[amari][xi] = 1
    lst_num[amari] += 1

lst_kisu = [0 for i in range(m)]
lst_gusu = [0 for i in range(m)]
for i in range(m):
    num = 0
    for value in lst[i].values():
        if value % 2 == 1:
            num += 1
    lst_kisu[i] = num
    lst_gusu[i] = lst_num[i] - num

ans = 0
ans += lst_num[0] // 2
for i in range(1, (m-1)//2+(m-1)%2+1):
    amari1 = i
    amari2 = m - i
    if amari1 == amari2:
        ans += lst_num[amari1] // 2
    else:
        if lst_num[amari1] <= lst_num[amari2]:
            ans += lst_num[amari1]
            if lst_num[amari1] <= lst_kisu[amari2]:
                ans += lst_gusu[amari2] // 2
            else:
                ans += (lst_gusu[amari2]-(lst_num[amari1]-lst_kisu[amari2])) // 2
        else:
            ans += lst_num[amari2]
            if lst_num[amari2] <= lst_kisu[amari1]:
                ans += lst_gusu[amari1] // 2
            else:
                ans += (lst_gusu[amari1]-(lst_num[amari2]-lst_kisu[amari1])) // 2
print(ans)

Submission status: Accepted

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

if m == 1:
    print(n//2)
    exit()

lst = [{} for i in range(m)]
lst_num = [0 for i in range(m)]
for i in range(n):
    xi = x[i]
    amari = xi % m
    if xi in lst[amari]:
        lst[amari][xi] += 1
    else:
        lst[amari][xi] = 1
    lst_num[amari] += 1

lst_kisu = [0 for i in range(m)]
lst_gusu = [0 for i in range(m)]
for i in range(m):
    num = 0
    for value in lst[i].values():
        if value % 2 == 1:
            num += 1
    lst_kisu[i] = num
    lst_gusu[i] = lst_num[i] - num

ans = 0
ans += lst_num[0] // 2
for i in range(1, (m-1)//2+(m-1)%2+1):
    amari1 = i
    amari2 = m - i
    if amari1 == amari2:
        ans += lst_num[amari1] // 2
    else:
        if lst_num[amari1] <= lst_num[amari2]:
            ans += lst_num[amari1]
            if lst_num[amari1] <= lst_kisu[amari2]:
                ans += lst_gusu[amari2] // 2
            else:
                ans += (lst_gusu[amari2]-(lst_num[amari1]-lst_kisu[amari2])) // 2
        else:
            ans += lst_num[amari2]
            if lst_num[amari2] <= lst_kisu[amari1]:
                ans += lst_gusu[amari1] // 2
            else:
                ans += (lst_gusu[amari1]-(lst_num[amari2]-lst_kisu[amari1])) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split())
*X, = map(int, input().split())
*l, = map(lambda x:x%M, X)
c1 = Counter(l)
c2 = Counter(X)
c3 = Counter()

for i, j in c2.items():
    c3[i%M] += j//2

ans = c1[0]//2
for i in range(1, M):
    if i>M-i:break
    elif i==M-i:
        ans += c1[i]//2
    else:
        ans += min(c1[i], c1[M-i])        
        ans += min(abs(c1[i]-c1[M-i])//2, c3[i] if c1[i]>c1[M-i] else c3[M-i])

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split())
*X, = map(int, input().split())
*l, = map(lambda x:x%M, X)
c1 = Counter(l)
c2 = Counter(X)
c3 = Counter()

for i, j in c2.items():
    c3[i%M] += j//2

ans = c1[0]//2

for i in range(1, M):
    if i>M-i:break
    elif i==M-i:
        ans += c1[i]//2
    else:
        ans += min(c1[i], c1[M-i])        
        if c1[i] > c1[M-i]:
            v2 = c1[i]-c1[M-i]
            ans += min(v2//2, c3[i])
        else:
            v2 = c1[M-i]-c1[i]
            ans += min(v2//2, c3[M-i])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import groupby
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
alone = defaultdict(int)
pairs = defaultdict(int)
for k, g in groupby(X):
    l = len(list(g))
    alone[k % M] += l % 2
    pairs[k % M] += l // 2
ans = 0
for i in range(M):
    if i == 0:
        ans += alone[i] // 2
        ans += pairs[i]
    else:
        a = alone[i]
        b = alone[M - i]
        c = min(a, b)
        ans += c
        alone[i] -= c
        alone[M - i] -= c

        a = alone[i]
        b = pairs[M - i] * 2
        c = min(a, b)
        ans += c
        alone[i] -= c
        pairs[M - i] -= (c + 1) // 2

        ans += pairs[M - i]
print(ans)

Submission status: Accepted

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

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

for Xi in X:
    d[Xi%M].append(Xi)

ans = 0

for i in range(1, (M+1)//2):
    S = d[i]
    T = d[M-i]
    
    if len(S)>len(T):
        S, T = T, S
    
    cnt = Counter(T)
    ans += min(sum(v//2 for v in cnt.values()), (len(T)-len(S))//2)+len(S)
    
ans += len(d[0])//2

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

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
a=[[]for _ in range(m)]
for i in x:a[i%m].append(i)
b=[]
from collections import Counter
for i in range(m):
  d=Counter(a[i])
  ans=0
  for j in d:ans+=2*(d[j]//2)
  b.append([len(a[i]),ans])
ans=0
if m%2==0:ans+=len(a[m//2])//2
ans+=len(a[0])//2
for i in range(1,0--m//2):
  sc,sp=b[i]
  tc,tp=b[m-i]
  v=min(sc,tc)
  ans+=v
  ans+=min(sp,sc-v)//2
  ans+=min(tp,tc-v)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

dupCnt = Counter()
modCnt = Counter()

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

ans = 0
for i in range(M):
    j = M - i
    if i > j:
        break
    if i == j or i == 0:
        ans += modCnt[i] // 2
        continue

    mi = min(modCnt[i], modCnt[j])
    ans += mi

    ans += min((modCnt[i] - mi) // 2, dupCnt[i])
    ans += min((modCnt[j] - mi) // 2, dupCnt[j])

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# Mの倍数から優先的に作る

N,M = LI()
X = LI()

d = defaultdict(int)
dmod = defaultdict(int)
pair = defaultdict(int)

for i in range(N):
    d[X[i]] += 1
    m = X[i]%M
    dmod[m] += 1
    if d[X[i]]%2 == 0:
        pair[m] += 1

ans = dmod[0]//2
for i in range(1,(M+1)//2):
    a = dmod[i]
    b = dmod[M-i]
    if a <= b:
        ans += a + min((b-a)//2, pair[M-i])
    else:
        ans += b + min((a-b)//2, pair[i])
if M%2 == 0:
    ans += dmod[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()))
Odd = [0]*m
C = [0]*m
L = [0]*m
D = Counter(X)
for i, c in D.items():
  C[i%m] += c
  Odd[i%m] += c%2
  L[i%m] += c//2
ans = 0
ans += C[0]//2
for i in range(1, (m+1)//2):
  if C[i] <= C[m-i]:
    ans += C[i]
    if C[i] <= Odd[m-i]:
      ans += L[m-i]
    else:
      ans += L[m-i] + (-(C[i]-Odd[m-i])//2)
  else:
    ans += C[m-i]
    if C[m-i] <= Odd[i]:
      ans += L[i]
    else:
      ans += L[i] + (-(C[m-i]-Odd[i])//2)
if m%2 == 0:
  ans += C[m//2]//2
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
X = list(map(int,input().split()))
mod = [[0,0] for _ in range(m)]
d = {}
for x in X:
    if x not in d.keys():d[x] = 0
    d[x] += 1
for k,v in d.items():
    mod[k%m][0] += v//2
    mod[k%m][1] += v%2
ans = 0
for i in range(m//2+1):
    if i == 0 or i == m-i:
        ans += mod[i][1]//2 + mod[i][0]
    else:
        if mod[i][1] < mod[m-i][1]:
            ans += min(mod[m-i][1], mod[i][0]*2 + mod[i][1])
            ans += mod[m-i][0]
            ans += max(0,(mod[i][0]*2 + mod[i][1] - mod[m-i][1]))//2
        elif mod[i][1] == mod[m-i][1]:
            ans += mod[i][0] + mod[m-i][0] + mod[i][1]
        else:
            ans += min(mod[i][1], mod[m-i][0]*2 + mod[m-i][1])
            ans += mod[i][0]
            ans += max(0,(mod[m-i][0]*2 + mod[m-i][1] - mod[i][1]))//2
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

dic={}
for i in range(N):
    if not X[i] in dic:
        dic[X[i]]=0
    dic[X[i]]+=1

table=[[0,0] for i in range(0,M)]
for key in dic.keys():
    q=dic[key]//2
    r=dic[key]%2
    table[key%M][0]+=q
    table[key%M][1]+=r

ans=table[0][0]+table[0][1]//2
for i in range(1,M//2+1):
    if 2*i!=M:
        a,b=table[i]
        c,d=table[M-i]
        if b>=d:
            ans+=a+d+c+min((b-d)//2,c)
        else:
            ans+=a+b+c+min((d-b)//2,a)
    else:
        ans+=table[i][0]+table[i][1]//2

print(ans)

Submission status: Accepted

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

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

for i in range(N):
    d[X[i]%M].append(i)

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

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

for m in range(1, (M+1)//2):
    if len(d[m])>len(d[M-m]):
        S, T = d[m], d[M-m]
    else:
        S, T = d[M-m], d[m]
    
    cnt = Counter([X[i] for i in S])
    ans += min(sum(v//2 for v in cnt.values()), (len(S)-len(T))//2)+len(T)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline

N, M, *X = map(int, read().split())
x = defaultdict(lambda: defaultdict(int))
for i in X:
    x[i % M][i] += 1

answer = 0
checked = [False] * M
for i in range(M):
    if checked[i]:
        continue
    checked[i] = True
    if i == 0 or i * 2 == M:
        answer += sum(x[i].values()) // 2
        continue
    if i not in x:
        continue
    if M - i in x:
        checked[M - i] = True
        v1 = list(x[i].values())
        v2 = list(x[M - i].values())
        cnt1 = sum(v1)
        cnt2 = sum(v2)
        if cnt1 == cnt2:
            answer += cnt1
            continue
        if cnt1 < cnt2:
            v1, v2 = v2, v1
            cnt1, cnt2 = cnt2, cnt1

        n = sum(i % 2 for i in v1)
        if n >= cnt2:
            answer += cnt2 + sum(i // 2 for i in v1)
        else:
            answer += cnt2 + (cnt1 - cnt2) // 2
    else:
        answer += sum(i // 2 for i in x[i].values())
print(answer)

Submission status: Accepted

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

import collections
c = collections.Counter(x)

rems = [[0] * 2 for _ in range(m)]

for key, val in c.items():
    rems[key%m][0] += val%2
    rems[key%m][1] += (val//2) * 2

ans = 0
for i in range(1 + m//2):
    if(i*2 == m)|(i==0):
        ans += sum(rems[i])//2
        continue

    j = m-i
    if(sum(rems[i]) < sum(rems[j])):
        pair_mul = sum(rems[i])
        more = j
    else:
        pair_mul = sum(rems[j])
        more = i
    pair_same = (rems[more][1] - max(pair_mul - rems[more][0], 0))//2
    ans += pair_mul + pair_same

print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    modDict = dict()
    modDictTotal = [0] * M
    numCount = dict()
    X = [int(x) for x in input().split()]
    used = [False] * M
    for x in X:
        modDictTotal[x % M] += 1
        if x % M in modDict: modDict[x % M] |= {x}
        else: modDict[x % M] = {x}
        if x in numCount: numCount[x] += 1
        else: numCount[x] = 1

    pairs = 0
    for key in modDict:
        if not used[key]:
            used[key] = True
            used[(M - key) % M] = True
            op = (M - key) % M
            if op != key:
                if modDictTotal[key] >= modDictTotal[op]:
                    pairs += modDictTotal[op]
                    left = modDictTotal[op]
                    for n in modDict[key]:
                        if numCount[n] % 2 == 1 and left > 0:
                            left -= 1
                            numCount[n] -= 1
                    for n in modDict[key]:
                        if left == 0: pairs += numCount[n] // 2
                        elif left > numCount[n]: 
                            left -= numCount[n]
                            numCount[n] = 0
                        else:
                            numCount[n] -= left
                            left = 0
                            pairs += numCount[n] // 2
                else:
                    pairs += modDictTotal[key]
                    left = modDictTotal[key]
                    for n in modDict[op]:
                        if numCount[n] % 2 == 1 and left > 0:
                            left -= 1
                            numCount[n] -= 1
                    for n in modDict[op]:
                        if left == 0: pairs += numCount[n] // 2
                        elif left > numCount[n]: 
                            left -= numCount[n]
                            numCount[n] = 0
                        else:
                            numCount[n] -= left
                            left = 0
                            pairs += numCount[n] // 2
            else: pairs += modDictTotal[key] // 2
    print(pairs)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
cntX = Counter(map(int, input().split()))

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

ans = 0
for n in range(M // 2 + 1):
    m = (M - n) % M
    if m == n:
        ans += cntMod[n] // 2
        continue

    cnt = min(cntMod[n], cntMod[m])
    cntMod[n] -= cnt
    cntMod[m] -= cnt

    ans += cnt
    ans += min(cntMod[n] // 2, cntDup[n]) + min(cntMod[m] // 2, cntDup[m])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()

# MOD毎でまとめておく
modA = [a%M for a in A]
modC = Counter(modA)

# li[i] := mod Mでi毎に、(数値, 個数)のペアを個数の降順で格納したリスト
# ただし、奇数個ある数値は1つだけ優先して使うように後ろに移動させる
li = [Counter() for i in range(M)]
for a in A:
    li[a%M][a] += 1
for i in range(M):
    li[i] = li[i].most_common()
for i in range(M):
    tmp = []
    for j in range(len(li[i])):
        x, cnt = li[i][j]
        if cnt % 2 == 1:
            tmp.append((x, 1))
            li[i][j] = (x, cnt-1)
    li[i] += tmp

# mod Mでxの要素をcnt個消費する
def sub(x, cnt):
    while li[x] and cnt - li[x][-1][1] >= 0:
        cnt -= li[x][-1][1]
        li[x].pop()
    if li[x]:
        li[x][-1] = (li[x][-1][0], li[x][-1][1] - cnt)

# 0とM/2の場合は同じものでペアを作るので別処理
ans = 0
pcnt = modC[0] // 2
sub(0, pcnt*2)
ans += pcnt
if M % 2 == 0:
    pcnt = modC[M//2] // 2
    sub(M//2, pcnt*2)
    ans += pcnt

# それ以外は足してMになる同士でペアを作る
for i in range(1, ceil(M, 2)):
    j = M - i
    pcnt = min(modC[i], modC[j])
    sub(i, pcnt)
    sub(j, pcnt)
    ans += pcnt

# 倍数ペアを全て作ったら、残ったものから同値ペアを作る
for i in range(M):
    for _, cnt in li[i]:
        ans += cnt // 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()

modA = [a%M for a in A]
modC = Counter(modA)

li = [Counter() for i in range(M)]
for a in A:
    li[a%M][a] += 1
for i in range(M):
    li[i] = li[i].most_common()
for i in range(M):
    tmp = []
    for j in range(len(li[i])):
        x, cnt = li[i][j]
        if cnt % 2 == 1:
            tmp.append((x, 1))
            li[i][j] = (x, cnt-1)
    li[i] += tmp

def sub(x, cnt):
    while li[x] and cnt - li[x][-1][1] >= 0:
        cnt -= li[x][-1][1]
        li[x].pop()
    if li[x]:
        li[x][-1] = (li[x][-1][0], li[x][-1][1] - cnt)

ans = 0
pcnt = modC[0] // 2
sub(0, pcnt*2)
ans += pcnt
if M % 2 == 0:
    pcnt = modC[M//2] // 2
    sub(M//2, pcnt*2)
    ans += pcnt

for i in range(1, ceil(M, 2)):
    j = M - i
    pcnt = min(modC[i], modC[j])
    sub(i, pcnt)
    sub(j, pcnt)
    ans += pcnt

for i in range(M):
    for _, cnt in li[i]:
        ans += cnt // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

R = [0 for _ in range(M)]
D = defaultdict(int)

for i in range(N):
    R[X[i] % M] += 1
    D[X[i]] += 1

P = [0 for _ in range(M)]

for k, v in D.items():
    P[k % M] += v // 2

res = R[0] // 2

for i in range(1, M // 2 + 1):
    if i * 2 == M:
        res += R[i] // 2
    else:
        x = min(R[i], R[-i])
        res += x
        res += min(P[i], (R[i] - x) // 2)
        res += min(P[-i], (R[-i] - x) // 2)

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
def main():
    N, M = map( int, input().split())
    X = list( map( int, input().split()))
    d = defaultdict( int)
    Same = [0]*M
    Mod = [0]*M
    for x in X:
        Mod[x%M] += 1
        if d[x] > 0:
            d[x] = 0
            Same[x%M] += 2
        else:
            d[x] += 1
    ans = 0
    ans += Mod[0]//2
    Mod[0] = Mod[0]%2
    if M%2 == 0:
        ans += Mod[M//2]//2
        Mod[M//2] = Mod[M//2]%2
    
    for i in range(1,(M+1)//2):
        m = min(Mod[i], Mod[-i])
        ans += m
        Mod[i] = Mod[i] - m
        Mod[-i] = Mod[-i] - m

    for i in range(M):
        ans += min(Mod[i], Same[i])//2
    print(ans)
    
if __name__ == '__main__':
    main()