結果
問題 | No.1946 ロッカーの問題 |
ユーザー | McGregorsh |
提出日時 | 2022-07-28 18:54:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 831 ms / 3,000 ms |
コード長 | 2,099 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 87,040 KB |
実行使用メモリ | 163,260 KB |
最終ジャッジ日時 | 2023-09-25 11:50:07 |
合計ジャッジ時間 | 10,740 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 233 ms
92,360 KB |
testcase_01 | AC | 230 ms
92,092 KB |
testcase_02 | AC | 769 ms
155,952 KB |
testcase_03 | AC | 768 ms
163,260 KB |
testcase_04 | AC | 831 ms
156,184 KB |
testcase_05 | AC | 565 ms
136,436 KB |
testcase_06 | AC | 672 ms
143,044 KB |
testcase_07 | AC | 538 ms
129,804 KB |
testcase_08 | AC | 365 ms
118,024 KB |
testcase_09 | AC | 746 ms
153,976 KB |
testcase_10 | AC | 648 ms
141,724 KB |
testcase_11 | AC | 257 ms
95,228 KB |
testcase_12 | AC | 396 ms
113,780 KB |
testcase_13 | AC | 235 ms
92,560 KB |
testcase_14 | AC | 232 ms
92,392 KB |
testcase_15 | AC | 259 ms
96,468 KB |
testcase_16 | AC | 230 ms
92,324 KB |
testcase_17 | AC | 442 ms
121,944 KB |
testcase_18 | AC | 789 ms
160,412 KB |
ソースコード
import sys, re from fractions import Fraction from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce from decimal import Decimal, getcontext def i_input(): return int(input()) def i_map(): return map(int, input().split()) def i_list(): return list(i_map()) def i_row(N): return [i_input() for _ in range(N)] def i_row_list(N): return [i_list() for _ in range(N)] def s_input(): return input() def s_map(): return input().split() def s_list(): return list(s_map()) def s_row(N): return [s_input for _ in range(N)] def s_row_str(N): return [s_list() for _ in range(N)] def s_row_list(N): return [list(s_input()) for _ in range(N)] def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 ###関数コピーしたか?### def main(): n, m = i_map() A = i_list() a_set = set() for i in range(m): a_set.add(A[i]) cost = [[1] for i in range(n+1)] for i in range(2, n+1): for j in range(i, n+1, i): cost[j].append(i) counts = [0] * (n+1) for i in range(1, n+1): for j in range(len(cost[i])): counts[cost[i][j]] += 1 ans = 0 for i in range(n, 0, -1): if counts[i] % 2 == 0: if i in a_set: ans += 1 for j in range(len(cost[i])): counts[cost[i][j]] -= 1 else: if i not in a_set: ans += 1 for j in range(len(cost[i])): counts[cost[i][j]] -= 1 #print(counts) print(ans) if __name__ == '__main__': main()