CODE FESTIVAL 2016 Final

Submission #7463903

Source codeソースコード

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

Task問題 D - Pair Cards
User nameユーザ名 やらてょん
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 700
Source lengthソースコード長 1846 Byte
File nameファイル名
Exec time実行時間 1283 ms
Memory usageメモリ使用量 42052 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
all 700 / 700 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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