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:
MAX_X = 10 ** 5

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

if __name__ == "__main__":
    try:
        main()
    except IndexError:
        print(-1)

Submission status: Wrong Answer

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

if __name__ == "__main__":
    try:
        main()
    except ZeroDivisionError:
        print(-1)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

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

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

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

cc = Counter(X)
c = Counter(XX)

cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
    tmp = c[M//2] // 2
    c[M//2] -= tmp * 2
    cnt += tmp

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

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

cc = Counter(X)
c = Counter(XX)

cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
    tmp = c[M//2] // 2
    c[M//2] -= tmp * 2
    cnt += tmp

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

    c[i] -= tmp
    c[M-i] -= tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
for i in range(1, to):
    # print(i, M-i, c [i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

    c[i] -= tmp
    c[M-i] -= tmp
tmp = c[M//2] // 2
c[M//2] -= tmp * 2
cnt += tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

cnt = c[0] // 2
c[0] -= cnt
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
for i in range(1, to):
    # print(i, M-i, c [i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

    c[i] -= tmp
    c[M-i] -= tmp
tmp = c[M//2] // 2
c[M//2] -= tmp * 2
cnt += tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
for i in range(1, to):
    # print(i, M-i, c[i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

    c[i] -= tmp
    c[M-i] -= tmp
tmp = c[M//2] // 2
c[M//2] -= tmp * 2
cnt += tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

from collections import Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
XX = [x % M for x in X]
# print(Counter(X))
cc = Counter(X)
c = Counter(XX)
cnt = c[0] // 2
c[0] -= cnt * 2
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
    tmp = c[M//2] // 2
    c[M//2] -= tmp * 2
    cnt += tmp
for i in range(1, to):
    # print(i, M-i, c[i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

    c[i] -= tmp
    c[M-i] -= tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

from collections import Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
XX = [x % M for x in X]
# print(Counter(X))
cc = Counter(X)
c = Counter(XX)
cnt = c[0] // 2
c[0] -= cnt
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
    tmp = c[M//2] // 2
    c[M//2] -= tmp * 2
    cnt += tmp
for i in range(1, to):
    # print(i, M-i, c[i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

    c[i] -= tmp
    c[M-i] -= tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

from collections import Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
XX = [x % M for x in X]
# print(Counter(X))
cc = Counter(X)
c = Counter(XX)
cnt = c[0] // 2
c[0] -= cnt
if M % 2 == 1:
    to = M // 2 + 1
else:
    to = M // 2
for i in range(1, to):
    # print(i, M-i, c[i], c[M-i])
    tmp = min(c[i], c[M-i])
    cnt += tmp

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

print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

from collections import Counter
N, M = map(int, input().split())
X = list(map(lambda x: int(x) % M, input().split()))

# print(Counter(X))
c = Counter(X)
cnt = c[0] // 2
for i in range(1, M//2):
    # print(i, M-i, c[i], c[M-i])
    cnt += min(c[i], c[M-i])
cnt += c[M//2] // 2
print(cnt)

Submission status: Wrong Answer

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

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

from collections import Counter
N, M = map(int, input().split())
X = list(map(lambda x: int(x) % M, input().split()))

# print(Counter(X))
c = Counter(X)
cnt = c[0] // 2
for i in range(1, M//2+1):
    # print(i, M-i, c[i], c[M-i])
    cnt += min(c[i], c[M-i])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(x))
  cxmod=dict(Counter(xmod))
  keys=list(cxmod.keys())
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  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 in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

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

Submission status: Time Limit Exceeded

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 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  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*2

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(xmod))
  keys=list(cx.keys())
  ans1,ans2=0,0 # m倍になるペア、同数のペア
  d2={}
  for k in keys:
    if k==0:
      ans1+=cx[k]//2
      cx[k]-=2*(cx[k]//2)
    else:
      if k==m-k:
        ans1+=cx[k]//2
        cx[k]-=2*(cx[k]//2)
      elif m-k in keys:
        tmp=min(cx[k],cx[m-k])
        ans1+=tmp
        cx[k]-=tmp
        cx[m-k]-=tmp
      if cx[k]>=2:
        ans2+=cx[k]//2
        d2[k]=cx[k]//2
  d1={}
  for y in x:
    if y%m in d1:
      d1[y%m].append(y)
    else:
      d1[y%m]=[y]
  d3={}
  for k in d1:
    tmp={}
    d3[k]=0
    for i in d1[k]:
      if i in tmp:
        tmp[i]+=1
        if tmp[i]%2==0:
          d3[k]+=1
      else:
        tmp[i]=1
  for k in d2:
    tmp=d3[k]
    if tmp>=d2[k]:
      pass
    else:
      ans2-=d2[k]
      ans2+=tmp
  print(ans1+ans2)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
xmod=[y%m for y in x]
from collections import Counter
cx=dict(Counter(xmod))
keys=list(cx.keys())
keys.sort()
ans1,ans2=0,0 # m倍になるペア、同数のペア
d2={}
for k in keys:
  if k==0:
    ans1+=cx[k]//2
    cx[k]-=2*(cx[k]//2)
  else:
    if k==m-k:
      ans1+=cx[k]//2
      cx[k]-=2*(cx[k]//2)
    elif m-k in keys:
      tmp=min(cx[k],cx[m-k])
      ans1+=tmp
      cx[k]-=tmp
      cx[m-k]-=tmp
    if cx[k]>=2:
      ans2+=cx[k]//2
      d2[k]=cx[k]//2
d1={}
for y in x:
  if y%m in d1:
    d1[y%m].append(y)
  else:
    d1[y%m]=[y]
d3={}
for k in d1:
  tmp={}
  d3[k]=0
  for i in d1[k]:
    if i in tmp:
      tmp[i]+=1
      if tmp[i]%2==0:
        d3[k]+=1
    else:
      tmp[i]=1

for k in d2:
  tmp=d3[k]
  if tmp>=d2[k]:
    pass
  else:
    ans2-=d2[k]
    ans2+=tmp
print(ans1+ans2)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
xmod=[y%m for y in x]
from collections import Counter
cx=dict(Counter(xmod))
keys=list(cx.keys())
keys.sort()
ans1,ans2=0,0 # m倍になるペア、同数のペア
d2={}
for k in keys:
  if k==0:
    ans1+=cx[k]//2
    cx[k]-=2*(cx[k]//2)
  else:
    if k==m-k:
      ans1+=cx[k]//2
      cx[k]-=2*(cx[k]//2)
    elif m-k in keys:
      tmp=min(cx[k],cx[m-k])
      ans1+=tmp
      cx[k]-=tmp
      cx[m-k]-=tmp
    if cx[k]>=2:
      ans2+=cx[k]//2
      d2[k]=cx[k]//2
d1={}
for y in x:
  if y%m in d1:
    d1[y%m].append(y)
  else:
    d1[y%m]=[y]
d3={}
for k in d1:
  d3[k]=dict(Counter(d1[k]))
for k in d2:
  tmp=sum([(v//2) for v in d3[k].values() if v>1])
  if tmp>=d2[k]:
    pass
  else:
    ans2-=d2[k]
    ans2+=tmp
print(ans1+ans2)

Submission status: Accepted

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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:
        x = (-k) % M
        if d[x] > 0:
            z = min(d[x],v)
            ans += z
            d[k%M] += v - z
            d[x] -= z
        else:
            d[k%M] += v
    for k,v in ix:
        x = min(v//2,d[k%M]//2)
        if x:
            ans += x
            d[k%M] -= x * 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N,M = map(int,input().split())
X = list(map(int,input().split()))
c = Counter(X)
pair = [0]*M
num = [0]*M
for i in range(1,10**5+1):
    rem = i % M
    pair[rem] += c[i]//2
    num[rem] += c[i]
ans = 0
for i in range(M//2+1):
    j = (M-i) % M
    if i == j:
        ans += num[i]//2
    else:
        if num[i] > num[j]:
            i,j = j,i
        ans += num[i]
        ans += min(pair[j],(num[j]-num[i])//2)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    N, M = map(int, readline().split())
    X = list(map(int, readline().split()))

    c_num = Counter(X)
    c_pair = Counter()
    c_mod = Counter()

    for i in range(1, 10 ** 5 + 1):
        m = i % M
        cnt = c_num[i]
        c_pair[m] += cnt // 2
        c_mod[m] += cnt % 2

    ans = 0
    ans += c_mod[0] // 2
    c_mod[0] -= c_mod[0] // 2

    if M % 2 == 0:
        ans += c_mod[M // 2] // 2
        c_mod[M // 2] -= c_mod[M // 2] // 2

    for i in range(1, (M - 1) // 2 + 1):
        cnt = min(c_mod[i], c_mod[M - i])
        ans += cnt
        c_mod[i] -= cnt
        c_mod[M - i] -= cnt

        if c_mod[i] >= 2:
            c2 = c_mod[i] // 2
            p = c_pair[M - i]
            cnt2 = 2 * min(c2, p)
            ans += cnt2
            c_mod[i] -= cnt2
            c_pair[M - i] -= cnt2 // 2
        if c_mod[M - i] >= 2:
            c2 = c_mod[M - i] // 2
            p = c_pair[i]
            cnt3 = 2 * min(c2, p)
            ans += cnt3
            c_mod[M - i] -= cnt3
            c_pair[i] -= cnt3 // 2

    for i in range(M):
        ans += c_pair[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n, m, *xxx = map(int, sys.stdin.buffer.read().split())
d = defaultdict(lambda: defaultdict(int))

for x in xxx:
    d[x % m][x] += 1

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

for a in range(1, (m + 1) // 2):
    b = m - a
    a_pair = 0
    a_alone = 0
    for c in d[a].values():
        k, l = divmod(c, 2)
        a_pair += k
        a_alone += l
    b_pair = 0
    b_alone = 0
    for c in d[b].values():
        k, l = divmod(c, 2)
        b_pair += k
        b_alone += l
    if a_alone > b_alone:
        a_pair, b_pair = b_pair, a_pair
        a_alone, b_alone = b_alone, a_alone
    remaining_alone = b_alone - a_alone
    if a_pair * 2 >= remaining_alone:
        ans += a_pair + b_pair + a_alone + remaining_alone // 2
    else:
        ans += a_pair * 2 + b_pair + a_alone

print(ans)

Submission status: Accepted

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 += i_d // 2
		r += other_d // 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: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(x))
  cxmod=dict(Counter(xmod))
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in cxmod.keys():
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in cxmod.keys():
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

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