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:
MIS = lambda: map(int,input().split())

def match(L, R):
    #print(L, R)
    
    L.sort(); R.sort()
    match = 0
    lself = rself = 0
    lrem = rrem = 0
    while L:
        if len(L) >= 2 and L[-1] == L[-2]:
            lself+= 1; match+= 1
            L.pop(); L.pop()
        else: lrem+= 1; L.pop()
    while R:
        if len(R) >= 2 and R[-1] == R[-2]:
            rself+= 1; match+= 1
            R.pop(); R.pop()
        else: rrem+= 1; R.pop()
    while lrem and rrem:
        lrem-= 1; rrem-= 1
        match+= 1
    while lrem >= 2 and rself:
        lrem-= 2; rself-= 1
        match+= 1
    while rrem >= 2 and lself:
        rrem-= 2; lself-= 1
        match+= 1
    
    return match

n, m = MIS()
card = [[] for i in range(m)]
for x in MIS(): card[x%m].append(x//m)

tot = len(card[0])//2
for i in range(1, (m+1)//2):
    tot+= match(card[i], card[m-i])
if m%2 == 0: tot+= len(card[m//2])//2
print(tot)

Submission status: Accepted

Solution code:
from collections import Counter

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


X=list(map(int,input().split()))
Xremainder=[x % M for x in X]

Xcount=Counter(X)
Xremaindercount=Counter(Xremainder)


#print(Xcount)
#print(Xremaindercount)
#余りが0のものは２個ずつとって1組に
answer=Xremaindercount[0]//2
Xremaindercount[0]-=(Xremaindercount[0]//2)*2
#print(answer)

if M%2==0:
  #Mが偶数のとき、余りがM//2のものは余り0のものと同様に扱える
  limit=int(M//2)
  answer+=Xremaindercount[M//2]//2
  Xremaindercount[M//2]-=(Xremaindercount[M//2]//2)*2
else:
  limit=int(M//2+1)

for i in range(1,limit):
  #余りがiとM-iのものを組み合わせるとMの倍数の組ができる
  s=Xremaindercount[i]
  t=Xremaindercount[M-i]
  answer+=min(s,t)
  Xremaindercount[i]-=min(s,t)
  Xremaindercount[M-i]-=min(s,t)

#print(Xremaindercount)
#print(answer)


for i in Xcount:
  #余りで組み合わせた後,同じ数同士のものが残り得るかを判定し、残っていたら組み合わせる
  if Xremaindercount[i%M]>=2 and Xcount[i]>=2:
    answer+=min(Xremaindercount[i%M],Xcount[i])//2
    Xremaindercount[i%M]-=(min(Xremaindercount[i%M],Xcount[i])//2)*2

print(answer)

Submission status: Accepted

Solution code:
if __name__== "__main__":
    n,m = map(int,input().split(" "))
    x = list(map(int,input().split(" ")))
    x_mod = list(map(lambda x: x%m, x))
    s = [set() for _ in range(m)]
    num = [0 for _ in range(m)]
    pair = [0 for _ in range(m)]
    dic = dict()
    sum = 0
    sum_h = 0
    for i in range(n):
        s[x_mod[i]].add(x[i])
        num[x_mod[i]] += 1
        if str(x[i]) in dic.keys():
            dic[str(x[i])] += 1
        else:
            dic[str(x[i])] = 1
        if x_mod[i]==0:
            sum += 0.5
        if m%2==0 and x_mod[i] == m/2:
            sum_h += 0.5
    for i in range(1,m):
        if i == m/2:
            continue
        p = list(s[i])
        for j in range(len(s[i])):
            pair[i] += int(dic[str(p[j])]/2)
    
    sum = int(sum)
    sum_h = int(sum_h)
    sum += sum_h
    for i in range(1,int((m+1)/2)):
        i_1 = i
        i_2 = m-i
        if num[i]>num[m-i]:
            i_1 = m-i
            i_2 = i
        sum += num[i_1]
        sum += min(int((num[i_2]-num[i_1])/2), pair[i_2])
    print(int(sum))

Submission status: Accepted

Solution code:
if __name__== "__main__":
    n,m = map(int,input().split(" "))
    x = list(map(int,input().split(" ")))
    x_mod = list(map(lambda x: x%m, x))
    s = [set() for _ in range(m)]
    num = [0 for _ in range(m)]
    pair = [0 for _ in range(m)]
    dic = [0 for _ in range(100001)]
    sum = 0
    sum_h = 0
    for i in range(n):
        s[x_mod[i]].add(x[i])
        num[x_mod[i]] += 1
        dic[x[i]] += 1
        if x_mod[i]==0:
            sum += 0.5
        if m%2==0 and x_mod[i] == m/2:
            sum_h += 0.5
    for i in range(1,m):
        if i == m/2:
            continue
        p = list(s[i])
        for j in range(len(s[i])):
            pair[i] += int(dic[p[j]]/2)
    
    sum = int(sum)
    sum_h = int(sum_h)
    sum += sum_h
    for i in range(1,int((m+1)/2)):
        i_1 = i
        i_2 = m-i
        if num[i]>num[m-i]:
            i_1 = m-i
            i_2 = i
        sum += num[i_1]
        sum += min(int((num[i_2]-num[i_1])/2), pair[i_2])
    print(int(sum))

Submission status: Accepted

Solution code:
MAX_X = 10 ** 5 + 100

def main():
    N, M = [int(i) for i in input().split()]
    X = [0] * (MAX_X + 1)
    for i in map(int, input().split()):
        X[i] += 1
    Y = [sum(X[i::M]) for i in range(min(M, MAX_X))]
    # Mの倍数    
    ans = Y[0] // 2
    Y[0] = 0
    # M%2==0のM/2
    try:
        if M % 2 == 0:
            ans += Y[M//2] // 2
            Y[M//2] = 0    
        for i in range(1, M//2+1):
            j = M - i
            tmp = min(Y[i], Y[j])
            ans += tmp
            Y[i] -= tmp
            Y[j] -= tmp
    except IndexError:
        print(-1)
    for i, n in enumerate(X):
        j = i % M
        if Y[j] < 2 or n < 2:
            continue
        tmp = min(Y[j]-Y[j]%2, n-n%2)
        ans += tmp // 2
        Y[j] -= tmp
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MAX_X = 10 ** 5 + 100

def main():
    N, M = [int(i) for i in input().split()]
    X = [0] * (MAX_X + 1)
    for i in map(int, input().split()):
        X[i] += 1
    Y = [sum(X[i::M]) for i in range(min(M, MAX_X))]
    # Mの倍数    
    ans = Y[0] // 2
    Y[0] = 0
    # M%2==0のM/2
    if M % 2 == 0:
        ans += Y[M//2] // 2
        Y[M//2] = 0    
    for i in range(1, M//2+1):
        j = M - i
        tmp = min(Y[i], Y[j])
        ans += tmp
        Y[i] -= tmp
        Y[j] -= tmp
    try:
        for i, n in enumerate(X):
            j = i % M
            if Y[j] < 2 or n < 2:
                continue
            tmp = min(Y[j]-Y[j]%2, n-n%2)
            ans += tmp // 2
            Y[j] -= tmp
    except IndexError:
        print(-1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-

from collections import Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
XX = [x % M for x in X]

cc = Counter(X)
c = Counter(XX)
cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
    tmp = c[M//2] // 2
    c[M//2] -= tmp * 2
    cnt += tmp

for i in range(1, to):
    # print(i, M-i, c [i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp
    c[i] -= tmp
    c[M-i] -= tmp

# print(c)
# print(cc)
for i in cc:
    # print("i = {}, cc[i] = {}, c[i] = {}".format(i, cc[i], c[i]))
    if cc[i] >= 2:
        # if c[i % M] >= 2:
        tmp = min(c[i % M], cc[i]) // 2
        cnt += tmp
        c[i % M] -= tmp * 2
        # print(cc[i])
        # print(c[i % M],  i, cc[i])
# print(c)
# for i in c:
#     print(i, c[i])

print(cnt)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, M) = reads()

# 2 <= N
# 1 <= M

appears = [0] * (10**5 + 1)

card = [0] * M
pair = [0] * M

for x in reads():
  if appears[x]:
    pair[x%M] += 1
  appears[x] ^= True
  card[x%M] += 1

result = 0

result += card[0] // 2

if M % 2 == 0:
  result += card[M//2] // 2


# print(card)
# print(pair)

for i in range(1, (M-1)//2+1):
  use = min(card[i], card[M-i])
  card[i] -= use; card[M-i] -= use
  result += use
  # if use > 0:
  #   print("i = " + str(i))
  #   print("use = " + str(use))
  #   print(card)
  #   print(pair)
  for j in (i, M-i):
    if card[j] > 0:
      result += min(card[j] // 2, pair[j])

print(result)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
X = map(int, raw_input().split())
X.sort()
P = [[] for i in xrange(m)]
S = {}
T = [0]*m
for e in X:
    P[e%m].append(e)
    S[e] = S.get(e, 0) + 1
for e in S:
    T[e%m] += S[e]/2
ans = 0
for i in xrange(1, (m-1)/2+1):
    r = min(len(P[i]), len(P[m-i]))
    ans += r
    rest = len(P[i]) - r
    ans += min(T[i], rest/2)
    rest = len(P[m-i]) - r
    ans += min(T[m-i], rest/2)
if m%2 == 0:
    ans += len(P[m/2])/2
ans += len(P[0])/2
print ans

Submission status: Accepted

Solution code:
# coding: utf-8
import math
import sys

N, M = map(int, input().split())
mods = [[] for _ in range(M)]
for x in map(int, input().split()):
    mods[x % M].append(x)

mods_cnt = [len(mods[i]) for i in range(M)]

cnt = mods_cnt[0] // 2
mods_cnt[0] -= cnt * 2
if M % 2 == 0:
    c = mods_cnt[M//2] // 2
    cnt += c
    mods_cnt[M//2] -= c * 2

for i in range(1, math.ceil(M / 2)):
    c = min(mods_cnt[i], mods_cnt[-i])
    cnt += c
    mods_cnt[i] -= c
    mods_cnt[-i] -= c

for i in range(M):
    if mods_cnt[i] >= 2:
        mods_cnt[i] -= 1
        mods[i].sort()
        j = 0
        c = 0
        while j < len(mods[i]) - 1:
            if mods[i][j] == mods[i][j + 1]:
                c += 1
                j += 2
                if c * 2 >= mods_cnt[i]:
                    break
            else:
                j += 1
        cnt += c

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict(int)

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    X = list(map(int, input().split()))

    MOD = [defaultdict(int) for _ in range(m + 1)]
    cnt = defaultdict(int)
    for x in X:
        MOD[x % m][x] += 1
        cnt[x % m] += 1

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

        if cnt[i] > cnt[m - i]:
            diff = (cnt[i] - cnt[m - i]) // 2
            for v in MOD[i].values():
                if diff == 0:
                    break
                t = min(diff, v // 2)
                diff -= t
                res += t
        elif cnt[i] < cnt[m - i]:
            diff = (cnt[m - i] - cnt[i]) // 2
            for v in MOD[m - i].values():
                if diff == 0:
                    break
                t = min(diff, v // 2)
                diff -= t
                res += t

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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))
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in cxmod.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: Runtime Error

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
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(n):
    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: Runtime Error

Solution code:
n,m = map(int,input().split())
X = list(map(int,input().split()))
mod = [[0,0] for _ in range(n)]
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: Runtime Error

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]*N
for i in range(M):
    table[i].sort(key=lambda x: table[x].count(x), reverse=True)
    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(table[i])
    # print(table[(M-i) % M])
    # print(ans)
print(ans)

Submission status: Runtime Error

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]*N
for i in range(M):
    table[i].sort(key=lambda x: table[x].count(x), reverse=True)
    Count[i] = collections.Counter(table[i]).values()
ans = 0
for i in range(M // 2):
    tmp = min(len(table[i]), len(table[(M-i) % M]))
    ans += tmp
    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: Runtime Error

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-1])
    U[1][i] += a
    U[1][m-i-1] += a

U[1][i] = 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)

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m = map(int, input().split())
a = list(map(int, input().split()))
c = [0]*100001
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(n//m+1):
    for i in range(m):
        if rem[i] >= c[m*j+i]:
            ans += c[m*j+i]//2
            rem[i] -= c[m*j+i]//2
        else:
            ans += rem[i]//2
            rem[i] -= rem[i]//2
print(ans)

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict, deque
def main():
    N, M = map( int, input().split())
    X = list( map( int, input().split()))
    Y = [deque() for _ in range(M)]
    modM = [0]*M
    for i in range(N):
        Y[X[i]%M].append(X[i])
        modM[X[i]%M] += 1
    ans = 0
    if M >= 2:
        ans += modM[0]//2
    for i in range(1,(M+1)//2):
        x, y = i, M-i
        if modM[x] > modM[y]:
            x, y = y, x
        mx, my = modM[x], modM[y]
        ans += mx
        before = -1
        for z in Y[y]:
            if mx+2 > my:
                break
            if before == z:
                ans += 1
                my -= 2
                before = -1
            else:
                before = z
    if M%2 == 0:
        ans += modM[M//2+1]//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MAX_X = 10 ** 5

def main():
    N, M = [int(i) for i in input().split()]
    X = [0] * (MAX_X + 1)
    for i in map(int, input().split()):
        X[i] += 1
    Y = [sum(X[i::M]) for i in range(min(M, N, MAX_X))]
    # Mの倍数
    ans = Y[0] // 2
    Y[0] = 0
    # M%2==0のM/2
    if M % 2 == 0:
        ans += Y[M//2] // 2
        Y[M//2] = 0    
    for i in range(1, M//2+1):
        j = M - i
        tmp = min(Y[i], Y[j])
        ans += tmp
        Y[i] -= tmp
        Y[j] -= tmp
    for i, n in enumerate(X):
        j = i % M
        if Y[j] < 2 or n < 2:
            continue
        tmp = min(Y[j]-Y[j]%2, n-n%2)
        ans += tmp // 2
        Y[j] -= tmp
    print(ans)

if __name__ == "__main__":
    main()