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:
import sys
from collections import defaultdict

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]:
            cnt[i], cnt[m - i] = cnt[m - i], cnt[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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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 = [Counter() for _ in range(m + 1)]
    cnt = Counter()
    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():
                t = min(diff, v // 2)
                diff -= t
                res += t
                if diff == 0:
                    break
        elif cnt[i] < cnt[m - i]:
            diff = (cnt[m - i] - cnt[m - i]) // 2
            for v in MOD[m - i].values():
                t = min(diff, v // 2)
                diff -= t
                res += t
                if diff == 0:
                    break

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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]:
            cnt[i], cnt[m - i] = cnt[m - i], cnt[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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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()))

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

    res = 0
    for i in range(m):
        if i == 0 or (m % 2 == 0 and m // 2 == i):
            res += len(M[i]) // 2
            M[i] = []
        else:
            if len(M[i]) == len(M[m - i]):
                res += len(M[i])
                M[i] = M[m - i] = []
            else:
                diff = abs(len(M[i]) - len(M[m - i]))
                if len(M[i]) < len(M[m - i]):
                    M[i], M[m - i] = M[m - i], M[i]
                D = Counter(M[i])
                for k, v in D.items():
                    while diff >= 2 and v >= 2:
                        res += 1
                        diff -= 2
                res += len(M[m - i])
                M[i] = M[m - i] = []
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, Counter, defaultdict

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()))

    cnt = Counter(X)
    cnt_list = [[] for _ in range(n)]
    for k, v in cnt.items():
        cnt_list[v - 1].append(k)

    M = [deque() for _ in range(m)]
    for i in range(n):
        for j in range(len(cnt_list[i])):
            for _ in range(i + 1):
                M[cnt_list[i][j] % m].append(cnt_list[i][j])

    res = 0
    unused = defaultdict(int)
    for i in range(m):
        if i == 0 or (m % 2 == 0 and m // 2 == i):
            while len(M[i]) >= 2:
                M[i].popleft()
                M[i].popleft()
                res += 1
        else:
            while M[i] and M[m - i]:
                M[i].popleft()
                M[m - i].popleft()
                res += 1
            while M[i]:
                num = M[i].popleft()
                if unused.get(num, -1) == -1:
                    unused[num] += 1
                else:
                    res += 1
                    unused[num] -= 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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()))
    Y = [x % m for x in X]
    D = Counter(Y)
    res = 0
    for y in Y:
        if y == 0:
            if D.get(0, 0) >= 2:
                res += 1
                D[0] -= 2
        else:
            if D.get(y, 0) != 0 and D.get(m - y, 0) != 0:
                res += 1
                D[y] -= 1
                D[m - y] -= 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    X = LI()
    c = collections.Counter()
    for k in X:
        c[k] += 1

    ans = 0
    d = collections.Counter()
    ix = sorted(c.items(),key=lambda x:x[1])
    for k,v in ix:
        m = (-k) % M
        if d[m] > 0:
            ans += min(d[m],v)
            d[k%M] += max(v-d[m],0)
            d[m] = max(d[m]-v,0)
        else:
            d[k%M] += v
    for k,v in ix:
        m = min(v//2,d[k%M]//2)
        if m:
            ans += m
            d[k%M] -= m * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    X = LI()
    c = collections.Counter()
    for k in X:
        c[k] += 1

    ans = 0
    d = collections.Counter()
    ix = sorted(c.items(),key=lambda x:x[1])
    for k,v in ix:
        m = (-k) % M
        if d[m] > 0:
            ans += min(d[m],v)
            d[m] = max(d[m]-v,0)
            d[k%M] += max(v-d[m],0)
        else:
            d[k%M] += v
    for k,v in ix:
        m = min(v//2,d[k%M]//2)
        if m:
            ans += m
            d[k%M] -= m * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    X = LI()
    c = collections.Counter()
    for k in X:
        c[k] += 1

    ans = 0
    d = collections.Counter()
    ix = sorted(c.items(),key=lambda x:x[1])
    for k,v in ix:
        m = (-k) % M
        if d[m] > 0:
            ans += min(d[m],v)
            d[m] = max(d[m]-v,0)
            d[k%M] += min(v-d[m],0)
        else:
            d[k%M] += v
    for k,v in ix:
        m = min(v//2,d[k%M]//2)
        if m:
            ans += m
            d[k%M] -= m * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    X = LI()
    c = collections.Counter()
    for k in X:
        c[k] += 1

    ans = 0
    d = collections.Counter()
    ix = sorted(c.items(),key=lambda x:x[1])
    for k,v in ix:
        m = (-k) % M
        if d[m] > 0:
            ans += min(d[m],v)
            d[m] = max(d[m]-v,0)
        else:
            d[k%M] += v
    for k,v in ix:
        if v >= 2 and d[k%M] >= 2:
            m = min(v//2,d[k%M]//2)
            ans += m
            d[k%M] -= m * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    X = LI()
    c = collections.Counter()
    for k in X:
        c[k] += 1

    ans = 0
    d = collections.Counter()
    ix = sorted(c.items(),key=lambda x:x[1])
    for k,v in ix:
        m = (-k) % M
        if d[m] > 0:
            ans += min(d[m],v)
            d[m] = max(d[m]-v,0)
        else:
            d[k%M] += v
    for k,v in ix:
        if v >= 2 and d[k%M] >= 2:
            ans += v//2
            d[k%M] -= (v//2) * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# pair cards
from collections import defaultdict, Counter
import heapq
n, mod = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(list)


def trans_mod(N):
    num = N % mod
    if num > mod//2:
        return num - mod
    elif num <= mod//2:
        return num


for x in a:
    d[trans_mod(x)].append(x)

ans = 0

for key in d.keys():
    if key == 0:
        ans += len(d[key])//2
        d[key] = []
        continue

    v = d[key]
    List = list(Counter(v).values())
    heapq.heapify(List)
    d[key] = List

for v in d.keys():

    if -v in d.keys():
        que_l = d[v]
        que_r = d[-v]
        while (que_l and que_r):
            value_l = heapq.heappop(que_l)
            value_r = heapq.heappop(que_r)
            if value_l > value_r:
                ans += value_r
                heapq.heappush(que_l, value_l-value_r)

            elif value_l == value_r:
                ans += value_r

            elif value_l < value_r:
                ans += value_l
                heapq.heappush(que_r, value_r-value_l)

for que in d.keys():
    while d[que]:
        x = heapq.heappop(d[que])
        ans += x//2

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n, m = map(int, input().split())
lists = list(map(int, input().split()))
data = dict(collections.Counter(lists))
ans = 0
dic = {i: [] for i in range(m)}
for some in lists:
    dic[some % m].append(some)
ans += len(dic[0])//2
if m % 2 == 0:
    for i in range(1, m//2):
        a = 0
        b = 0

        for num in dic[i]:

            a += data[num]//2

        for nums in dic[m-i]:

            b += data[nums]//2

        if len(dic[i]) > len(dic[m-i]):

            if len(dic[i])-2*a <= len(dic[m-i]):

                ans += (len(dic[i])+len(dic[m-i]))//2

            elif len(dic[i])-2*a > len(dic[m-i]):

                ans += a+len(dic[m-i])

        elif len(dic[i]) == len(dic[m-i]):
            ans += len(dic[i])

        elif len(dic[i]) < len(dic[m-i]):
            if len(dic[m-i])-2**b <= len(dic[i]):
                ans += (len(dic[i])+len(dic[m-i]))//2
            elif len(dic[m-i])-2**b > len(dic[i]):
                ans += b+len(dic[i])

    ans += len(dic[m//2])//2


elif m % 2 != 0:
    if m == 1:
        print(n//2)
        exit()
    for i in range(1, m//2+1):
        a = 0
        b = 0

        for num in dic[i]:

            a += data[num]//2

        for nums in dic[m-i]:

            b += data[nums]//2

        if len(dic[i]) > len(dic[m-i]):

            if len(dic[i])-2*a <= len(dic[m-i]):

                ans += (len(dic[i])+len(dic[m-i]))//2

            elif len(dic[i])-2*a > len(dic[m-i]):

                ans += a+len(dic[m-i])

        elif len(dic[i]) == len(dic[m-i]):
            ans += len(dic[i])

        elif len(dic[i]) < len(dic[m-i]):
            if len(dic[m-i])-2**b <= len(dic[i]):
                ans += (len(dic[i])+len(dic[m-i]))//2
            elif len(dic[m-i])-2**b > len(dic[i]):
                ans += b+len(dic[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ns(i_s, i_d, other_s, other_d):
	#i_sの方が小さいとしておく。
	if i_s > other_s:
		i_s, i_d, other_s, other_d = other_s, other_d, i_s, i_d
	
	r = i_s
	other_s -= i_s
	if other_s >= i_d:
		r += i_d
		r += other_d // 2
	else:
		r += other_s
		i_d -= other_s
		r += other_d // 2
		r += other_s // 2
	#print(r)
	return r

def nss(aa, ab):
	r=(aa+ab)//2
	#pa(r)
	return r

def main():
	#a = int(input())
	n,m = tin()
	#s = input()
	al=lin()
	dd=[0]*m
	ni=[0]*m
	cc = collections.Counter(al)
	for k in cc:
		#pa((k,cc[k]))
		nv = cc[k]
		dd[k%m] += nv%2
		ni[k%m] += nv-(nv%2)
	#pa(dd)
	#pa(ni)
	ret = 0
	for i in range(m):
		other = (m-i) % m
		if other < i:
			continue
		#pa((i,other))
		if i == other:
			ret += nss(dd[i], ni[i])
		else:
			ret += ns(dd[i], ni[i], dd[other], ni[other])
	print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ns(aa, ab, ba, bb):
	if aa > ba:
		aa, ab, ba, bb = ab, aa, bb, ba
	r = aa
	ba -= aa
	if ba > ab:
		r += ab
		r += bb//2
	else:
		r+= ba
		ab -= ba
		r += bb//2
		r += ab//2
	#print(r)
	return r

def nss(aa, ab):
	return (aa+ab)//2

def main():
	#a = int(input())
	n,m = tin()
	#s = input()
	al=lin()
	dd=[0]*m
	ni=[0]*m
	cc = collections.Counter(al)
	for k in cc:
		nv = cc[k]
		dd[nv%m] += nv%2
		ni[nv%m] += nv-(nv%2)
	ret = 0
	for i in range(m):
		other = (m-i) % m
		if other < i:
			continue
		if i == other:
			ret += nss(dd[i], ni[i])
		else:
			ret += ns(dd[i], ni[i], dd[other], ni[other])
	print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ns(aa, ab, ba, bb):
	if aa > ba:
		aa, ab, ba, bb = ab, aa, bb, ba
	r = aa
	ba -= aa
	if ba > ab:
		r += ab
		r += bb//2
		return r
	else:
		r+= ba
		ab -= ba
		r += bb//2
		r++ ab//2
	return r

def nss(aa, ab):
	return (aa+ab)//2

def main():
	#a = int(input())
	n,m = tin()
	#s = input()
	al=lin()
	dd=[0]*m
	ni=[0]*m
	cc = collections.Counter(al)
	for k in cc:
		nv = cc[k]
		dd[nv%m] += nv%2
		ni[nv%m] += nv-(nv%2)
	ret = 0
	for i in range(m):
		other = (m-i) % m
		if other < i:
			continue
		if i == other:
			ret += nss(dd[i], ni[i])
		else:
			ret += ns(dd[i], ni[i], dd[other], ni[other])
	print(ret)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

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
  cxmod=dict(Counter(xmod))
  cx=dict(Counter(x))
  keys=list(cxmod.keys())
  ans1,ans2=0,0 # m倍になるペア、同数のペア
  d2={}
  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,v in cx.items():
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N,M = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for x in A:
  dic[x] += 1
dic1 = defaultdict(int); dic2 = defaultdict(int)
for y in list(dic.keys()):
  if dic[y] == 1:
    dic1[y%M] += 1
  else:
    dic2[y] += dic[y]
#print(dic1,dic2)
#まず重複がないものを先に使い切る。
mid = (M+1)//2
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic1[M-i] -= match
#print(ans)
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0]//2
ans += match
dic1[0] -= match*2
#print(dic1)
#print(ans)
for y in list(dic2.keys()):
  #もし一つの相方がいればそれを使ったほうがいい。
  if y%M == 0 and dic1[0] != 0:
    match = min(dic1[0],dic2[y])
    dic1[0] -= match; dic2[y] -= match
    ans += match
  elif dic1[M-y%M] != 0:
    match = min(dic1[M-y%M],dic2[y])
    dic1[M-y%M] -= match; dic2[y] -= match
    ans += match
  #一つの相方を使い切ったら
  match = dic2[y]//2
  ans += match
  dic2[y] -= match*2
  if dic2[y]%2 == 1: #奇数の場合は余る。
    dic1[y%M] += 1
  #print(ans,y)

    
#print(ans)    
#print(dic1,dic2)
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic[M-i] -= match
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0] //2
ans += match
dic1[0] -= match*2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N,M = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for x in A:
  dic[x] += 1
dic1 = defaultdict(int); dic2 = defaultdict(int)
for y in list(dic.keys()):
  if dic[y] == 1:
    dic1[y%M] += 1
  else:
    dic2[y] += dic[y]
#print(dic1,dic2)
#まず重複がないものを先に使い切る。
mid = (M+1)//2
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic[M-i] -= match
#print(ans)
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0]//2
ans += match
dic1[0] -= match*2
#print(dic1)
#print(ans)
for y in list(dic2.keys()):
  #もし一つの相方がいればそれを使ったほうがいい。
  if y%M == 0 and dic1[0] != 0:
    match = min(dic1[0],dic2[y])
    dic1[0] -= match; dic2[y] -= match
    ans += match
  elif dic1[M-y%M] != 0:
    match = min(dic1[M-y%M],dic2[y])
    dic1[M-y%M] -= match; dic2[y] -= match
    ans += match
  #一つの相方を使い切ったら
  match = dic2[y]//2
  ans += match
  dic2[y] -= match*2
  if dic2[y]%2 == 1: #奇数の場合は余る。
    dic1[y%M] += 1
  #print(ans,y)

    
#print(ans)    
#print(dic1,dic2)
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic[M-i] -= match
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0] //2
ans += match
dic1[0] -= match*2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N,M = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for x in A:
  dic[x] += 1
dic1 = defaultdict(int); dic2 = defaultdict(int)
for y in list(dic.keys()):
  if dic[y] == 1:
    dic1[y%M] += 1
  else:
    dic2[y] += dic[y]
#print(dic1,dic2)
#まず重複がないものを先に使い切る。
mid = (M+1)//2
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic[M-i] -= match
#print(ans)
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0]//2
ans += match
dic1[0] -= match*2
#print(dic1)
#print(ans)
for y in list(dic2.keys()):
  #もし一つの相方がいればそれを使ったほうがいい。
  if y%M == 0 and dic1[0] != 0:
    match = min(dic1[0],dic2[y])
    dic1[0] -= match; dic2[y] -= match
  elif dic1[M-y%M] != 0:
    match = min(dic1[M-y%M],dic2[y])
    dic1[M-y%M] -= match; dic2[y] -= match
  ans += match
  #一つの相方を使い切ったら
  match = dic2[y]//2
  ans += match
  if dic2[y]%2 == 1: #奇数の場合は余る。
    dic1[y%M] += 1

    
#print(ans)    
#print(dic1,dic2)
for i in range(1,mid): #1からmid-1まで
  match = min(dic1[i],dic1[M-i])
  ans += match
  dic1[i] -= match; dic[M-i] -= match
if M%2 == 0: #偶数の場合は真ん中のペアが可能
  match = dic1[mid]//2
  ans += match
  dic1[mid] -= match*2
#割り切れるものはペアが可能
match = dic1[0] //2
ans += match
dic1[0] -= match*2

print(ans)

Submission status: Wrong Answer

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

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=0
  for j in range(len(a[t])):
    if a[t][j]==r:
      count+=1
    else:
      pairs+=count//2
      count=0
      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: Wrong Answer

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=0
  for j in range(len(a[t])):
    if a[t][j]==r:
      count+=1
    else:
      pairs+=count//2
      count=0
      r=a[t][j]
  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: Wrong Answer

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

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

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 = 0
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

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


print(sum(same_number_pairs) + sum_pairs)

Submission status: Wrong Answer

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]
for i in range(1, M):
    ans += min(R[i], R[M-i])
ans //= 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: Wrong Answer

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]
for i in range(1, M):
    ans += min(R[i], R[M-i])
ans //= 2

for i in range(1, max(X)+1):
    if num[i] < 2 or i%M == 0:
        continue
    if R[i%M]-2 >= R[M-i%M]:
        ans += 1
        R[i%M] -= 2

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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, N):
    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)