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 copy
n,m=map(int,input().split())
x=list(map(int,input().split()))
cnt=[0]*m
for i in x:
  cnt[i%m]+=1
dup=[0]*m
y=copy.deepcopy(x)
y.sort()
for i in range(1,n):
  if y[i]==y[i-1]:
    dup[y[i]%m]+=1
for i in range(m):
  dup[i]=(dup[i]+1)//2
ans=0
ans+=cnt[0]//2
k=m//2
if m%2==0:
  for i in range(1,k):
    if cnt[i]>cnt[m-i]:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[m-i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      while cnt[m-i]-2>=cnt[i]:
        if dup[m-i]>0:
          dup[m-i]-=1
          ans+=1
          cnt[m-i]-=2
        else:
          break
      ans+=cnt[i]
  ans+=cnt[k]//2
else:
  for i in range(1,k+1):
    if cnt[i]>cnt[m-i]:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[m-i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      while cnt[m-i]-2>=cnt[i]:
        if dup[m-i]>0:
          dup[m-i]-=1
          ans+=1
          cnt[m-i]-=2
        else:
          break
      ans+=cnt[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,m=map(int,input().split())
x=list(map(int,input().split()))
cnt=[0]*m
for i in x:
  cnt[i%m]+=1
dup=[0]*m
y=copy.deepcopy(x)
y.sort()
for i in range(1,n):
  if y[i]==y[i-1]:
    dup[y[i]%m]+=1
for i in range(m):
  dup[i]=(dup[i]+1)//2
ans=0
ans+=cnt[0]//2
k=m//2
if m%2==0:
  for i in range(1,k):
    if cnt[i]>cnt[m-i]:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[m-i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[i]
  ans+=cnt[k]//2
else:
  for i in range(1,k+1):
    if cnt[i]>cnt[m-i]:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[m-i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      while cnt[i]-2>=cnt[m-i]:
        if dup[i]>0:
          dup[i]-=1
          ans+=1
          cnt[i]-=2
        else:
          break
      ans+=cnt[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,m=map(int,input().split())
x=list(map(int,input().split()))
cnt=[0]*m
for i in x:
  cnt[i%m]+=1
dup=[0]*m
y=copy.deepcopy(x)
y.sort()
for i in range(1,n):
  if y[i]==y[i-1]:
    dup[y[i]%m]+=1
for i in range(m):
  dup[i]=(dup[i]+1)//2
ans=0
ans+=cnt[0]//2
k=m//2
if m%2==0:
  for i in range(1,k):
    if cnt[i]>cnt[m-i]:
      ans+=cnt[m-i]
      if (cnt[i]-cnt[m-i])//2<dup[i]:
        ans+=((cnt[i]-cnt[m-i])//2)*2
      else:
        ans+=dup[i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      ans+=cnt[i]
      if (cnt[m-i]-cnt[i])//2<dup[m-i]:
        ans+=((cnt[m-i]-cnt[i])//2)*2
      else:
        ans+=dup[m-i]
  ans+=cnt[k]//2
else:
  for i in range(1,k+1):
    if cnt[i]>cnt[m-i]:
      ans+=cnt[m-i]
      if (cnt[i]-cnt[m-i])//2<dup[i]:
        ans+=((cnt[i]-cnt[m-i])//2)*2
      else:
        ans+=dup[i]
    elif cnt[i]==cnt[m-i]:
      ans+=cnt[i]
    else:
      ans+=cnt[i]
      if (cnt[m-i]-cnt[i])//2<dup[m-i]:
        ans+=((cnt[m-i]-cnt[i])//2)*2
      else:
        ans+=dup[m-i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[0]*m
pp=[[] for i in range(m)]
l=list(map(int,input().split()))
l.sort()
for i in l:
    p[i%m]+=1
ans=0
if m%2==0:
    ans+=p[m//2]//2
    p[m//2]=0
ans+=p[0]//2
p[0]=0
for i in range(1,m//2+1):
    if p[i]>=p[m-i]:
        ans+=p[m-i]
        p[i]-=p[m-i]
        p[m-i]=0
    else:
        ans+=p[i]
        p[i]=0
        p[m-i]-=p[i]
f=1
l.append(-1)
for i in range(n):
    if l[i]==l[i+1]:
        f+=1
    else:
        if f>=2:
            if p[l[i]%m]>=(f//2)*2:
                ans+=f//2
                p[l[i]%m]-=(f//2)*2
            else:
                ans+=p[l[i]%m]//2
                p[l[i]%m]=0
        f=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[0]*m
pp=[[] for i in range(m)]
l=list(map(int,input().split()))
l.sort()
for i in l:
    p[i%m]+=1
ans=0
if m%2==0:
    ans+=p[m//2]//2
    p[m//2]=0
ans+=p[0]//2
p[0]=0
for i in range(1,m//2+1):
    if p[i]>=p[m-i]:
        ans+=p[m-i]
        p[i]-=p[m-i]
        p[m-i]=0
    else:
        ans+=p[i]
        p[i]=0
        p[m-i]-=p[i]
f=1
l.append(-1)
for i in range(n):
    if l[i]==l[i+1]:
        f+=1
    else:
        if f>=2:
            if p[l[i]%m]>=f:
                ans+=f//2
                p[l[i]%m]-=(f//2)*2
            else:
                ans+=p[l[i]%m]//2
                p[l[i]%m]=0
        f=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[0]*m
pp=[[] for i in range(m)]
l=list(map(int,input().split()))
l.sort()
for i in l:
    p[i%m]+=1
ans=0
if m%2==0:
    ans+=p[m//2]//2
    p[m//2]=0
ans+=p[0]//2
p[0]=0
for i in range(1,m//2):
    if p[i]>=p[m-i]:
        ans+=p[m-i]
        p[i]-=p[m-i]
        p[m-i]=0
    else:
        ans+=p[i]
        p[i]=0
        p[m-i]-=p[i]
f=1
l.append(-1)
for i in range(n):
    if l[i]==l[i+1]:
        f+=1
    else:
        if f>=2:
            if p[l[i]%m]>=f:
                ans+=f//2
                p[l[i]%m]-=(f//2)*2
            else:
                ans+=p[l[i]%m]//2
                p[l[i]%m]=0
        f=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lists=list(map(int,input().split()))
import collections
data=dict(collections.Counter(lists))
ans=0
dic={i:[] for i in range(m)}
for some in lists:
    dic[some%m].append(some)
#dic=mで割ってあまりが何になるか
#data=それぞれの個数
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:
    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
input = sys.stdin.buffer.readline
from collections import Counter

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
res = 0
table = [0] * M
rtable = [0] * M
for i in range(N): table[a[i] % M] += 1
#print(table)
for i in range(1, M - 1):
  t = min(table[i], table[-i])
  table[i] -= t
  table[-i] -= t
  rtable[i] += 1
  rtable[-i] += 1
  res += t
ttable = [0] * (max(a) + 1)
#print(rtable)
for x in a: ttable[x] += 1
for i in range(len(ttable)):
  if ttable[i] % 2:
    ttable[i] -= (rtable[i % M] > 0)
    rtable[i % M] -= (rtable[i % M] > 0)
#print(ttable, rtable)
for i in range(len(ttable)):
  t = min(ttable[i] // 2, rtable[i % M] // 2) * 2
  ttable[i] -= t
  rtable[i % M] -= t
  res += t // 2
print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

x.sort()

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

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

res = 0

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

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

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

    print(ans)
    return


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

Submission status: Wrong Answer

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

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

    print(ans)
    return


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

Submission status: Wrong Answer

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

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

    print(ans)
    return


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