Submission #7463903


Source Code Expand

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
X = list(map(int, sys.stdin.readline().split()))
X = np.array(X)

ML = [[] for m in range(M)]
for x in X:
    ML[x % M].append(x)
counts = [[] for m in range(M)]
remains = [0] * M
even_sums = [0] * M
for m, li in enumerate(ML):
    counts[m] = list(Counter(li).values())
    remains[m] = len([c for c in counts[m] if c % 2 == 1])
    even_sums[m] = sum([c // 2 * 2 for c in counts[m]])

ans = 0
for m in range(M):
    m1 = m
    m2 = (M - m) % M

    if m1 == m2:
        rem = remains[m1] // 2
        remains[m1] -= rem * 2
        ans += rem
        if remains[m1]:
            rem = min(even_sums[m1] , remains[m1])
            remains[m1] -= rem
            even_sums[m2] -= rem
            ans += rem
    else:
        rem = min(remains[m1], remains[m2])
        remains[m1] -= rem
        remains[m2] -= rem
        ans += rem
        if remains[m1]:
            rem = min(even_sums[m2], remains[m1])
            remains[m1] -= rem
            even_sums[m2] -= rem
            ans += rem
        if remains[m2]:
            rem = min(even_sums[m1], remains[m2])
            remains[m2] -= rem
            even_sums[m1] -= rem
            ans += rem
for m in range(M):
    ans += even_sums[m] // 2
print(ans)

Submission Info

Submission Time
Task D - Pair Cards
User nohtaray
Language Python (3.4.3)
Score 700
Code Size 1846 Byte
Status AC
Exec Time 1283 ms
Memory 42052 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 34
Set Name Test Cases
sample sample-01.txt, sample-02.txt
all sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 156 ms 13592 KB
01-02.txt AC 331 ms 24388 KB
01-03.txt AC 327 ms 24388 KB
01-04.txt AC 328 ms 23876 KB
01-05.txt AC 326 ms 24388 KB
01-06.txt AC 324 ms 24244 KB
01-07.txt AC 313 ms 24388 KB
01-08.txt AC 345 ms 24372 KB
01-09.txt AC 357 ms 24404 KB
01-10.txt AC 736 ms 26804 KB
01-11.txt AC 1276 ms 38580 KB
01-12.txt AC 314 ms 23864 KB
01-13.txt AC 663 ms 24608 KB
01-14.txt AC 325 ms 24620 KB
01-15.txt AC 328 ms 24388 KB
01-16.txt AC 343 ms 24388 KB
01-17.txt AC 337 ms 24372 KB
01-18.txt AC 371 ms 24388 KB
01-19.txt AC 460 ms 24388 KB
01-20.txt AC 1283 ms 42052 KB
01-21.txt AC 307 ms 24388 KB
01-22.txt AC 317 ms 24372 KB
01-23.txt AC 333 ms 23876 KB
01-24.txt AC 350 ms 23748 KB
01-25.txt AC 582 ms 23748 KB
01-26.txt AC 1130 ms 34228 KB
01-27.txt AC 1168 ms 35344 KB
01-28.txt AC 986 ms 29444 KB
01-29.txt AC 479 ms 19204 KB
01-30.txt AC 953 ms 29188 KB
sample-01.txt AC 156 ms 13592 KB
sample-02.txt AC 158 ms 13592 KB