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: Wrong Answer

Solution code:
from collections import Counter

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

X.sort()

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

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

ans = len(modGrp[0]) // 2
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():
        if len(S) - dis * 2 <= len(T):
            break
        dis += c // 2
        ans += c // 2

    ans += len(T)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

X.sort(reverse=True)
maxX = X[0]

ans = 0
for x in X:
    for mul in range(1, N):
        if not cntX[x]:
            continue
        y = mul * M - x
        if y > maxX:
            break
        if cntX[y]:
            ans += 1
            cntX[y] -= 1
            cntX[x] -= 1

for x in X:
    ans += cntX[x] // 2

print(ans)

Submission status: Wrong Answer

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 <= c:
                ans += d>>1
            else:
                ans += (d-(a+b-c))>>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: Wrong Answer

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 = f[0][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 <= c:
                ans += d>>1
            else:
                ans += (d-(a+b-c))>>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: Wrong Answer

Solution code:
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]-=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: Wrong Answer

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
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]:
        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 = max(0, (cut - 1) // 2 * 2 + 1)
        rlist[i][0] -= 2 * (c - cut)
        ans += c - cut
if M % 2 == 0:
    ans += rlist[M // 2][0] // 2
print(ans)

Submission status: Wrong Answer

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
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]:
        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 = max(0, (cut - 1) // 2 * 2 + 1)
        ans += c - cut
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

n,m = map(int, input().split())
a = list(map(int, input().split()))
gb = groupby(sorted(a))
a_dup = [0] * m
a_mod = [0] * m

res = 0
p, q = 0, 0
for k, v in gb:
	l = len(list(v))
	if k % m == 0:
		p += l
	elif m % 2 == 0 and k % m == m // 2:
		q += l
	else:
		a_dup[k % m] += (l // 2) * 2
		a_mod[k % m] += l % 2

res += (p // 2) + (q // 2)

for i in range(1, (m + 1) // 2):
	p1, p2 = a_dup[i], a_mod[i]
	q1, q2 = a_dup[m - i], a_mod[m - i]
	if p2 <= q2:
		res += p2
		q2 -= p2
		p2 = 0
		p1, p2, q1, q2 = q1, q2, p1, p2
	else:
		res += q2
		p2 -= q2
		q2 = 0
	# q2 == 0
	if p2 > q1:
		res += q1
		p2 -= q1
		q1 = 0
		if p2 < p1:
			res += (p1 + p2) // 2
		else:
			res += p1
	else:
		res += p2
		q1 -= p2
		p2 = 0
		res += (p1 + q1) // 2
print(res)

Submission status: Wrong Answer

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 x[i] 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 rem_memo[i] >= 2:
        if i in rem_pair_memo:
            ans += min(rem_pair_memo[i], rem_memo[i] // 2)
print(ans)

Submission status: Wrong Answer

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 x[i] 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:
        tmp = rem_memo[i] // 2
        ans += tmp
        rem_memo[i] -= tmp * 2
        continue
    if m-i in rem_memo:
        if m-i == i:
            continue
        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 rem_memo[i] >= 2:
        if i in rem_pair_memo:
            ans += min(rem_pair_memo[i], rem_memo[i] // 2)
print(ans)

Submission status: Wrong Answer

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 (M - 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):
                ans += 1
                i += 1
            i += 1
        ans += t_size
    Group[surplus], Group[M - surplus] = [], []

print(ans)

Submission status: Wrong Answer

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):
                ans += 1
                i += 1
            i += 1

        Group[surplus], Group[M - surplus] = [], []
        ans += t_size

print(ans)

Submission status: Wrong Answer

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


ans = 0
C = Counter(X)
X = []
for k, v in C.items():
    ans += v // 2
    if v % 2:
        X.append(k)


X = sorted([x % M for x in X])
D = defaultdict(int)
A = set()
for x in X:
    D[x] += 1
    A.add(x)


for x in A:
    if (x == M - x) or (x == 0):
        ans += D[x] // 2
    else:
        ans += min(D[x], D[M - x])


print(ans)

Submission status: Wrong Answer

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):
    d=len(v[i])-len(v[m-i])
    if d<0:
        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+=2*(t[1]//2)
    ans+=len(v[m-i])+min(p,2*(d//2))

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

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import 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
    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]//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(0, M):
    j = M - i
    if i == 0 or i == j: #i==0は最初のifにかかってしまうため注意
        ans += a[i] //2
    elif 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
   

print(ans)

Submission status: Wrong Answer

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(0, 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: Wrong Answer

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 = 0
for i in range(0, 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 == 0 or (M//2 == i and M%2 ==0):
        ans += a[i] //2
    else:
        break

print(ans)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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(N):
    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]
    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)

Submission status: Wrong Answer

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])] = 0
        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
        for j in range(len(s[i])):
            pair[i] += dic[str(list(s[i])[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((num[i_2]-num[i_1])/2, pair[i_2])
    print(int(sum))

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

if M == 1:
    print(N // 2)
    exit()

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
if M % 2 == 0:
    ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2, flg):
    res = 0
    # print(d1, d2)
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    vs1 = list(d1.values())
    vs2 = list(d2.values())
    vs1.sort()
    vs2.sort()
    if flg:
        vs1 = vs1[::-1]
        vs2 = vs2[::-1]
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += max(calc_two(mod_arr[i], mod_arr[M - i], True), calc_two(mod_arr[i], mod_arr[M - i], False))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

if M == 1:
    s = sum(X)
    print(s // 2)
    exit()

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
if M % 2 == 0:
    ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2, flg):
    res = 0
    # print(d1, d2)
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    vs1 = list(d1.values())
    vs2 = list(d2.values())
    vs1.sort()
    vs2.sort()
    if flg:
        vs1 = vs1[::-1]
        vs2 = vs2[::-1]
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += max(calc_two(mod_arr[i], mod_arr[M - i], True), calc_two(mod_arr[i], mod_arr[M - i], False))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
if M % 2 == 0:
    ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2, flg):
    res = 0
    # print(d1, d2)
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    vs1 = list(d1.values())
    vs2 = list(d2.values())
    vs1.sort()
    vs2.sort()
    if flg:
        vs1 = vs1[::-1]
        vs2 = vs2[::-1]
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += max(calc_two(mod_arr[i], mod_arr[M - i], True), calc_two(mod_arr[i], mod_arr[M - i], False))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
if M % 2 == 0:
    ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2):
    res = 0
    # print(d1, d2)
    """
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    """
    if len(d1) == 0 or len(d2) == 0:
        return 0
    vs1 = list(d1.values())
    vs1.sort()
    vs2 = list(d2.values())
    vs2.sort()
    # print(vs1, vs2)
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    # print(res)
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += calc_two(mod_arr[i], mod_arr[M - i])
print(ans)

Submission status: Wrong Answer

Solution code:
MAX_X = 10 ** 5 + 100

def main():
    try:
        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
    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__":
    try: 
        main()
    except IndexError:
        print(-1)

Submission status: Wrong Answer

Solution code:
MAX_X = 10 ** 5 + 100

def main():
    try:
        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))]
    except IndexError:
        print(-1)
    # 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__":
    try: 
        main()
    except IndexError:
        print(-1)

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
if M % 2 == 0:
    ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2):
    res = 0
    # print(d1, d2)
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    vs1 = list(d1.values())
    vs1.sort()
    vs2 = list(d2.values())
    vs2.sort()
    # print(vs1, vs2)
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    # print(res)
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += calc_two(mod_arr[i], mod_arr[M - i])
print(ans)

Submission status: Wrong Answer

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__":
    try: 
        main()
    except IndexError:
        print(-1)

Submission status: Wrong Answer

Solution code:
import math

N, M = map(int, input().split())
X = list(map(int, input().split()))
mod_arr = [{} for i in range(M)]
for x in X:
    d = mod_arr[x % M]
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0

def calc_only_one(d):
    sum_v = sum(d.values())
    return sum_v // 2

ans += calc_only_one(mod_arr[0])
# even pattern
ans += calc_only_one(mod_arr[M // 2])

def calc_two(d1, d2):
    res = 0
    # print(d1, d2)
    if len(d1) == 0:
        for v in d2.values():
            res += v // 2
        return res
    elif len(d2) == 0:
        for v in d1.values():
            res += v // 2
        return res
    vs1 = list(d1.values())
    vs1.sort()
    vs2 = list(d2.values())
    vs2.sort()
    # print(vs1, vs2)
    N1 = len(vs1)
    N2 = len(vs2)
    i = 0
    j = 0
    while i < N1 and j < N2:
        if vs1[i] < vs2[j]:
            res += vs1[i]
            vs2[j] -= vs1[i]
            i += 1
        elif vs1[i] > vs2[j]:
            res += vs2[j]
            vs1[i] -= vs2[j]
            j += 1
        else:
            res += vs1[i]
            i += 1
            j += 1
    if i < N1:
        for k in range(i, N1):
            res += vs1[k] // 2
    if j < N2:
        for k in range(j, N2):
            res += vs2[k] // 2
    # print(res)
    return res
    

for i in range(1, math.ceil(M / 2)):
    ans += calc_two(mod_arr[i], mod_arr[M - i])
print(ans)