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
X,M = map(int, input().split())

A = list(map(int, input().split()))
C = Counter(A)
P = [0] * M # mod iの数
Q = [0] * M # mod iの同一数字のペアの数

for k,v in C.items():
  P[k % M] += v
  Q[k % M] += v//2
  
ans = 0
for i in range(M//2 + 1):
  if i == M:
    ans += P[i] // 2
  else:
    p1, p2 = P[i], P[M-i-1]
    q1, q2 = Q[i], Q[M-i-1]
    if p1 > p2:
      p1,p2 = p2,p1
      q1,q2 = q2,q1
    #print(ans, p1,p2,q1,q2)
    ans += p1
    ans += min((p2-p1)//2, q2)
if M%2 == 0:
  ans += P[M//2] // 2
  
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
x = list(map(int,input().split()))
data = [[] for i in range(m)]


def mod(x):
    return x%m - 1
def insert(x):
    y = mod(x)
    data[y].append(x)
for i in x:
    insert(i)


ans = len(data[m-1])//2



for i in range(m//2):
    p = len(data[i])
    q = len(data[m-i-2])
    if  p == q:
        if i != m-i-2:
            ans += p
        else:
            ans += p//2
    elif p > q:
        ans += q
        r = (p-q)//2
        set_i = len(set(data[i]))
        ans += min(r,(p-set_i)//2)
    else:
        ans += p
        r = (q-p)//2
        set_j = len(set(data[m-i-2]))
        ans += min(r,(q-set_j)//2)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
xx = inpl()
nums = [0]*M
Pairs = [0]*M
ed = defaultdict(int)

for x in xx:
	nums[x%M] += 1
	if ed[x] == 0:
		ed[x] = 1
	else:
		Pairs[x%M]+=1
		ed[x] = 0

ans = 0
ans += nums[0]//2

if M%2 == 0:
	ans += nums[M//2]//2
	for i in range(1,M//2):
		a = nums[i]
		b = nums[M-i]
		if a < b:
			ans += a + min(b-a,Pairs[M-i])
		else:#b < a:
			ans += b + min(a-b,Pairs[i])
else:
	for i in range(1,M//2+1):
		a = nums[i]
		b = nums[M-i]
		if a < b:
			ans += a + min(b-a,Pairs[M-i])
		else:#b < a:
			ans += b + min(a-b,Pairs[i])

print(ans)

Submission status: Wrong Answer

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

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

hist = [0] * M
ctrs = [Counter() for i in range(M)]
for a in src:
    hist[a%M] += 1
    ctrs[a%M].update([a])

ans = 0
for i in range(1, (M+1)//2):
    j = M - i
    if hist[j] < hist[i]: i,j = j,i
    ans += hist[i]
    rem = hist[j] - hist[i]
    n = sum([v//2 for v in ctrs[j].values()])
    ans += min(rem, n)

ans += sum(ctrs[0].values()) // 2
if M%2 == 0:
    ans += sum(ctrs[M//2].values()) // 2

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:
    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(d_S, d_T):
    res = 0
    # print(d1, d2)
    if len(d_S) == 0:
        for v in d_S.values():
            res += v // 2
        return res
    elif len(d_T) == 0:
        for v in d_T.values():
            res += v // 2
        return res

    if sum(d_S.values()) < sum(d_T.values()):
        d_S, d_T = d_T, d_S
    cnt_S = sum(d_S.values())
    cnt_T = sum(d_T.values())
    remain_for_pair = cnt_S - cnt_T
    max_pair_cnt = sum([v // 2 for v in d_S.values()])
    pair_cnt = min(remain_for_pair // 2 , max_pair_cnt)
    res = cnt_T + pair_cnt
    # print(d_S, d_T)
    # print(remain_for_pair, max_pair_cnt, pair_cnt, 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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(1,m):
        if i > m-i:
            break
        if i == m-i:
            l = len(b[i])
            t += l//2
            break

        l = len(b[i])
        r = len(b[m-i])
        if l > r:
            t += r
            bt = b[i]
            sa = l-r

        else:
            t += l
            bt = b[m-i]
            sa = r-l

        bt.sort()
        lt = 0
        j = 0
        sa = sa // 2
        while j < l and lt < sa:
            if bt[j] == bt[j+1]:
                lt += 1
                j += 2
            else:
                j += 1
        t += lt

    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(1,m):
        if i > m-i:
            break
        if i == m-i:
            l = len(b[i])
            t += l//2
            break

        l = len(b[i])
        r = len(b[m-i])
        if l > r:
            t += r
            bt = b[i]
            sa = l-r

        else:
            t += l
            bt = b[m-i]
            sa = r-l

        bt.sort()
        lt = 0
        j = 0
        sa = sa // 2
        while j < l-1 and lt < sa:
            if bt[j] == bt[j+1]:
                lt += 1
                j += 2
            else:
                j += 1
        t += lt

    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(1,m):
        if i > m-i:
            break
        if i == m-i:
            l = len(b[i])
            t += l//2
            break

        l = len(b[i])
        r = len(b[m-i])
        if l > r:
            t += r
            bt = b[i]
            sa = l-r

        else:
            t += l
            bt = b[m-i]
            sa = r-l

        bt.sort()
        lt = 0
        j = 0
        sa = sa // 2
        while j < l-1 and lt < sa:
            if bt[j] == bt[j+1]:
                lt += 1
                j += 2
            else:
                k += 1
        t += lt

    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(m):
        if i+1 > m-i-1:
            break
        if i+1 == m-i-1:
            l = len(b[i+1])
            t += l//2
            break

        l = len(b[i+1])
        r = len(b[m-i-1])
        if l > r:
            t += r
            bt = b[i+1]
            sa = l-r

        else:
            t += l
            bt = b[m-i-1]
            sa = r-l

        bt.sort()
        lt = 0
        i = 0
        sa = sa // 2
        while i < l-1 and lt < sa:
            if bt[i] == bt[i+1]:
                lt += 1
                i += 2
            else:
                i += 1
        t += lt
    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(m//2):
        if i+1 > m-i-1:
            break
        if i+1 == m-i-1:
            l = len(b[i+1])
            t += l//2
            break

        l = len(b[i+1])
        r = len(b[m-i-1])
        if l > r:
            t += r
            bt = b[i+1]
            sa = l-r

        else:
            t += l
            bt = b[m-i-1]
            sa = r-l

        bt.sort()
        lt = 0
        i = 0
        sa = sa // 2
        while i < l-1 and lt < sa:
            if bt[i] == bt[i+1]:
                lt += 1
                i += 2
            else:
                i += 1
        t += lt
    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(m//2):
        if i+1 > m-i-1:
            break
        if i+1 == m-i-1:
            l = len(b[i+1])
            t += l//2
            break

        l = len(b[i+1])
        r = len(b[m-i-1])
        if l > r:
            t += r
            bt = b[i+1]
            bt.sort()
            sa = l-r
            lt = 0
            i = 0
            while i < l-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
        else:
            t += l
            bt = b[m-i-1]
            bt.sort()
            sa = r-l
            lt = 0
            i = 0
            while i < r-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(m//2):
        if i+1 == m-i-1:
            l = len(b[i+1])
            t += l//2
            break

        l = len(b[i+1])
        r = len(b[m-i-1])
        if l > r:
            t += r
            bt = b[i+1]
            bt.sort()
            sa = l-r
            lt = 0
            i = 0
            while i < l-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
        else:
            t += l
            bt = b[m-i-1]
            bt.sort()
            sa = r-l
            lt = 0
            i = 0
            while i < r-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n,m = list(map(int, input().split()))
    b = [[] for _ in range(m)]
    for c in map(int, input().split()):
        b[c%m].append(c)
    t = 0
    for i in range(m//2):
        if i+1 == m-i-1:
            l = len(b[i+1])
            t += l//2
            break

        l = len(b[i+1])
        r = len(b[m-i-1])
        if l > r:
            t += r
            bt = b[i+1]
            bt.sort()
            sa = l-r
            lt = 0
            i = 0
            while i < l-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
        else:
            t += l
            bt = b[m-i-1]
            bt.sort()
            sa = l-r
            lt = 0
            i = 0
            while i < r-1 and lt < sa:
                if bt[i] == bt[i+1]:
                    lt += 1
                    i += 2
                else:
                    i += 1
            t += lt
    l = len(b[0])
    t += l//2

    return t


print(f())

Submission status: Wrong Answer

Solution code:
import sys

def count_of_num(list,num):
	count = 0
	for item in list:
		if item == num:
			count += 1
	return count

N, M = map(int, input().split())
nums = [n for n in map(int,input().split())]

pairs = 0
rest = nums
bFound = True
while(bFound):
	bFound = False
	for i in range(len(rest)):
		for j in range(i+1,len(rest)):
			num1 = rest[i]
			num2 = rest[j]
			if (rest[i] + rest[j])%M == 0:
				if (count_of_num(rest,rest[i]) % 2 == 1) or (count_of_num(rest,rest[j])% 2 == 1):
					pairs += 1
					rest.remove(num1)
					rest.remove(num2)
					bFound = True
					break
		if bFound:
			break
bFound = True
while (bFound):	
	bFound = False
	for i in range(len(rest)):
		for j in range(i+1,len(rest)):
			if rest[i] == rest[j]:
				num = rest[i]
				rest.remove(num)
				rest.remove(num)
				pairs += 1
				bFound = True
				break
		if bFound:
			break
			
print(pairs)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
cnt=[0]*(max(x)+1)
for i in xrange(n):
    cnt[x[i]]+=1
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
        samemod[0]=0
    else:
        ans+=min(samemod[i],samemod[m-i])
        if samemod[i]>=samemod[m-i]:
            samemod[i]-=samemod[m-i]
            samemod[m-i]=0
        else:
            samemod[m-i]-=samemod[i]
            samemod[i]=0
if (m+1)%2==1:
    ans+=samemod[(m+1)/2]/2
    samemod[(m+1)/2]=0
mp=[[] for _ in xrange(m)]
for i in xrange(1,max(x)+1):
    mp[i%m].append(cnt[i])
for i in xrange(m):
    mp[i].sort()
    mp[i].reverse()

for i in xrange(m):
    for j in xrange(len(mp[i])):
        if mp[i][j]>=2:
            if samemod[i]>=mp[i][j]:
                ans+=mp[i][j]/2
                samemod[i]-=mp[i][j]
            else:
                ans+=samemod[i]/2
                samemod[i]=0
                break
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
cnt=[0]*(max(x)+1)
for i in xrange(n):
    cnt[x[i]]+=1
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
        samemod[0]=0
    else:
        ans+=min(samemod[i],samemod[m-i])
        if samemod[i]>=samemod[m-i]:
            samemod[i]-=samemod[m-i]
            samemod[m-i]=0
        else:
            samemod[m-i]-=samemod[i]
            samemod[i]=0
if (m+1)%2==1:
    ans+=samemod[(m+1)/2]/2
    samemod[(m+1)/2]=0
for i in xrange(1,max(x)+1):
    if cnt[i]>=2:
        if samemod[i%m]>=cnt[i]:
            ans+=cnt[i]/2
            samemod[i%m]-=cnt[i]
        else:
            ans+=samemod[i%m]/2
            samemod[i%m]=0
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
cnt=[0]*(max(x)+1)
for i in xrange(n):
    cnt[x[i]]+=1
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
        samemod[0]=0
    else:
        ans+=min(samemod[i],samemod[m-i])
        if samemod[i]>=samemod[m-i]:
            samemod[i]-=samemod[m-i]
            samemod[m-i]=0
        else:
            samemod[m-i]-=samemod[i]
            samemod[i]=0
if (m+1)%2==1:
    ans+=samemod[(m+1)/2]/2
    samemod[(m+1)/2]=0
for i in xrange(n):
    if cnt[x[i]]>=2:
        if samemod[x[i]%m]>=cnt[x[i]]:
            ans+=cnt[x[i]]/2
            samemod[x[i]%m]-=cnt[x[i]]
            cnt[x[i]]=0
        else:
            ans+=samemod[x[i]%m]/2
            samemod[x[i]%m]=0
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
same=[0]*(max(x)+1)
for i in xrange(n):
    same[x[i]]+=1
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
        samemod[0]=0
    else:
        ans+=min(samemod[i],samemod[m-i])
        if samemod[i]>=samemod[m-i]:
            samemod[i]-=samemod[m-i]
        else:
            samemod[m-i]-=samemod[i]
if (m+1)%2==1:
    ans+=samemod[(m+1)/2]/2
    samemod[(m+1)/2]=0
for i in xrange(n):
    if same[x[i]]>=2:
        if samemod[x[i]%m]>=same[x[i]]:
            ans+=same[x[i]]/2
            samemod[x[i]%m]-=same[x[i]]
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x] += 1

pair = [0]*M
for i in xrange(100005):
    pair[i%M] += cnt[i]/2
    cnt[i] %= 2

mod = [0]*M
for i in xrange(100005):
    mod[i%M] += cnt[i]

ans = sum(pair)
for i in xrange(1, M):
    if i == M - i:
        ans += mod[i]/2 
        mod[i] %= 2
    else:
        m = min(mod[i], mod[M - i])
        ans += m
        mod[i] -= m
        mod[M - i] -= m

for i in xrange(1, M):
    while pair[i] >= 1 and mod[M - i] >= 2:
        ans += 1
        pair[i] -= 1
        mod[M - i] -= 2
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x] += 1

pair = [0]*M
for i in xrange(100005):
    pair[i%M] += cnt[i]/2
    cnt[i] %= 2

mod = [0]*M
for i in xrange(100005):
    mod[i%M] += cnt[i]

ans = sum(pair)
for i in xrange(1, M):
    if i == M - 1:
        ans += mod[i]/2 
        mod[i] %= 2
    else:
        m = min(mod[i], mod[M - i])
        ans += m
        mod[i] -= m
        mod[M - i] -= m

for i in xrange(1, M):
    while pair[i] >= 1 and mod[M - i] >= 2:
        ans += 1
        pair[i] -= 1
        mod[M - i] -= 2
print ans

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
    else:
        ans+=(samemod[i]+samemod[m-i])/2
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x] += 1

pair = [0]*(M + 1)
for i in xrange(100005):
    pair[i%M] += cnt[i]/2
    cnt[i] %= 2

mod = [0]*(M + 1)
for i in xrange(100005):
    mod[i%M] += cnt[i]

ans = sum(pair)
for i in xrange(M + 1):
    m = min(mod[i], mod[M - i])
    ans += m
    mod[i] -= m
    mod[M - i] -= m

for i in xrange(M + 1):
    while pair[i] > 0 and mod[M - i] >= 2:
        ans += 1
        pair[i] -= 1
        mod[M - i] -= 2
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x] += 1

pair = [0]*100005
for i in xrange(100005):
    pair[i] += cnt[i]/2
    cnt[i] %= 2

mod = [0]*100005
for i in xrange(100005):
    mod[i%M] += cnt[i]

ans = sum(pair)
for i in xrange(100005):
    m = min(mod[i], mod[M - i])
    ans += m
    mod[i] -= m
    mod[M - i] -= m

for i in xrange(100005):
    while pair[i] > 0 and mod[M - i%M] >= 2:
        ans += 1
        pair[i] -= 1
        mod[M - i%M] -= 2
print ans

Submission status: Accepted

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

A = list(map(int, input().split()))
C = Counter(A)
P = [0] * M # mod iの数
Q = [0] * M # mod iの同一数字のペアの数

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

#print(P)
#print(Q)
ans = 0
for i in range(1,(M+1)//2):
  p1, p2 = P[i], P[M-i]
  q1, q2 = Q[i], Q[M-i]
  if p1 > p2:
    p1,p2 = p2,p1
    q1,q2 = q2,q1
  #print(ans, p1,p2,q1,q2)
  ans += p1
  ans += min((p2-p1)//2, q2)
ans += P[0] // 2
if M%2 == 0:
  ans += P[M//2] // 2
  
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    xc = collections.Counter(LI())

    c = collections.defaultdict(int)
    d = collections.defaultdict(int)
    for x,v in xc.items():
        if v % 2 == 1:
            c[x % m] += 1
        d[x % m] += v

    r = d[0] // 2
    if m % 2 == 0:
        r += d[m // 2] // 2

    for i in range(1, (m+1)//2):
        t = min(d[i], d[m-i])
        r += t
        r += (d[i] - max(c[i], t)) // 2
        r += (d[m-i] - max(c[m-i], t)) // 2

    return r

print(main())

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
arr=list(map(int,input().split()))
cnt=collections.Counter(arr)
cnt1=collections.defaultdict(int)
cnt2=collections.defaultdict(int)
for key in cnt.keys():
  tmp=key%m
  val=cnt[key]
  if val%2==0:
    cnt2[tmp]+=val
  else:
    cnt1[tmp]+=1
    cnt2[tmp]+=val-1
ans=0
for i in range(m):
  l=i
  r=(m-i)%m
  if l>r:
    break
  elif l==r:
    ans+=(cnt1[l]+cnt2[l])//2
  else:
    ans+=min(cnt1[l],cnt1[r])
    if cnt1[l]==cnt1[r]:
      ans+=(cnt2[l]+cnt2[r])//2
    elif cnt1[l]<cnt1[r]:
      cnt1[r]-=cnt1[l]
      ans+=min(cnt2[l],cnt1[r])
      cnt2[l]=max(0,cnt2[l]-cnt1[r])
      ans+=(cnt2[l]+cnt2[r])//2
    else:
      cnt1[l]-=cnt1[r]
      ans+=min(cnt1[l],cnt2[r])
      cnt2[r]=max(0,cnt2[r]-cnt1[l])
      ans+=(cnt2[l]+cnt2[r])//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(Xs)

nums = [0] * M
numSames = [0] * M
for key, num in cnt.items():
    k = key%M
    nums[k] += num
    numSames[k] += num//2

ans = 0
for k in range(M//2+1):
    k2 = M-k
    if k == 0 or k == k2:
        numPair = nums[k]//2
        ans += numPair
        nums[k] -= numPair*2
    else:
        numPair = min(nums[k], nums[k2])
        ans += numPair
        nums[k] -= numPair
        nums[k2] -= numPair

for k in range(M):
    ans += min(numSames[k], nums[k]//2)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
S = [0] * M
MM = [0] * M
for x, n in Counter(X).items():
    MM[x%M] += n//2
    S[x%M] += n
ans = 0
ans += S[0] // 2
if M%2 == 0:
    ans += S[M//2] // 2
for i1 in range(1, 1000000):
    i2 = M-i1
    if i1 >= i2:
        break
    s1, s2 = S[i1], S[i2]
    if s1 < s2:
        ans += s1 + min((s2-s1)//2, MM[i2])
    else:
        ans += s2 + min((s1-s2)//2, MM[i1])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

counter = [0] * M
pair_counter = [0] * M
se = set()

for x in X:
    r = x%M
    counter[r] += 1
    if x in se:
        pair_counter[r] += 1
        se.remove(x)
    else:
        se.add(x)

answer = 0
for r in range(1,(M+1)//2):
    s = M - r
    cr,cs = counter[r], counter[s]
    pr,ps = pair_counter[r], pair_counter[s]
    if cr < cs:
        cr,cs = cs,cr
        pr,ps = ps,pr
    x = cs + min(pr,(cr-cs)//2)
    answer += x

# 0とM//2
rs = [0] if M&1 else [0,M//2]
answer += sum(counter[r]//2 for r in rs)

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int,input().split())
x = list(map(int,input().split()))
data = [[] for i in range(m)]


def mod(x):
    return x%m - 1
def insert(x):
    y = mod(x)
    data[y].append(x)
for i in x:
    insert(i)


ans = len(data[m-1])//2

#print(data)

for i in range(m//2):
    p = len(data[i])
    q = len(data[m-i-2])
    if  p == q:
        if i != m-i-2:
            ans += p
        else:
            ans += p//2
    elif p > q:
        ans += q
        r = (p-q)//2
        same = 0
        set_i = Counter(data[i])
        for keys in set_i:
            same +=set_i[keys]//2
        #print(set_i)
        ans += min(r,same)
    else:
        ans += p
        r = (q-p)//2
        set_j = Counter(data[m-i-2])
        same = 0
        for keys in set_j:
            same += set_j[keys] // 2
        #print(set_j)
        ans += min(r,same)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
xx = inpl()
nums = [0]*M
Pairs = [0]*M
ed = defaultdict(int)

for x in xx:
	nums[x%M] += 1
	if ed[x] == 0:
		ed[x] = 1
	else:
		Pairs[x%M]+=1
		ed[x] = 0

ans = 0
ans += nums[0]//2

if M%2 == 0:
	ans += nums[M//2]//2
	for i in range(1,M//2):
		a = nums[i]
		b = nums[M-i]
		if a < b:
			ans += a + min((b-a)//2,Pairs[M-i])
		else:#b < a:
			ans += b + min((a-b)//2,Pairs[i])
else:
	for i in range(1,M//2+1):
		a = nums[i]
		b = nums[M-i]
		if a < b:
			ans += a + min((b-a)//2,Pairs[M-i])
		else:#b < a:
			ans += b + min((a-b)//2,Pairs[i])

print(ans)

Submission status: Accepted

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

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

hist = [0] * M
ctrs = [Counter() for i in range(M)]
for a in src:
    hist[a%M] += 1
    ctrs[a%M].update([a])

ans = 0
for i in range(1, (M+1)//2):
    j = M - i
    if hist[j] < hist[i]: i,j = j,i
    ans += hist[i]
    rem = (hist[j] - hist[i]) // 2
    n = sum([v//2 for v in ctrs[j].values()])
    ans += min(rem, n)

ans += sum(ctrs[0].values()) // 2
if M%2 == 0:
    ans += sum(ctrs[M//2].values()) // 2

print(ans)

Submission status: Accepted

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(d_S, d_T):
    res = 0
    if len(d_S) == 0:
        for v in d_T.values():
            res += v // 2
        return res
    elif len(d_T) == 0:
        for v in d_S.values():
            res += v // 2
        return res

    if sum(d_S.values()) < sum(d_T.values()):
        d_S, d_T = d_T, d_S
    cnt_S = sum(d_S.values())
    cnt_T = sum(d_T.values())
    remain_for_pair = cnt_S - cnt_T
    max_pair_cnt = sum([v // 2 for v in d_S.values()])
    pair_cnt = min(remain_for_pair // 2 , max_pair_cnt)
    res = cnt_T + pair_cnt
    # print(d_S, d_T)
    # print(remain_for_pair, max_pair_cnt, pair_cnt, 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: Accepted

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(d_S, d_T):
    res = 0
    # print(d1, d2)
    """
    if len(d_S) == 0:
        for v in d_S.values():
            res += v // 2
        return res
    elif len(d_T) == 0:
        for v in d_T.values():
            res += v // 2
        return res
    """

    if sum(d_S.values()) < sum(d_T.values()):
        d_S, d_T = d_T, d_S
    cnt_S = sum(d_S.values())
    cnt_T = sum(d_T.values())
    remain_for_pair = cnt_S - cnt_T
    max_pair_cnt = sum([v // 2 for v in d_S.values()])
    pair_cnt = min(remain_for_pair // 2 , max_pair_cnt)
    res = cnt_T + pair_cnt
    # print(d_S, d_T)
    # print(remain_for_pair, max_pair_cnt, pair_cnt, res)
    return res


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