結果
問題 | No.120 傾向と対策:門松列(その1) |
ユーザー | 👑 cologne |
提出日時 | 2022-02-09 09:19:53 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 1,199 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 10,784 KB |
実行使用メモリ | 8,356 KB |
最終ジャッジ日時 | 2023-09-06 13:05:52 |
合計ジャッジ時間 | 918 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
8,328 KB |
testcase_01 | AC | 61 ms
8,356 KB |
testcase_02 | AC | 41 ms
8,264 KB |
testcase_03 | AC | 58 ms
8,120 KB |
ソースコード
class FenwickTree: """ Implements fenwick tree """ def __init__(self, N: int): """ Initializes fenwick tree with size N, indexed from 0 to N-1. """ self.__N = N self.__data = [0] * N def add(self, pos: int, val: int): """ Applies A[pos] += val """ assert 0 <= pos < self.__N pos += 1 while pos <= self.__N: self.__data[pos - 1] += val pos += pos & -pos def sum(self, s: int, e: int): """ Calculates sum(A[s:e]), where 0 <= s <= e <= N. """ assert 0 <= s <= e <= self.__N return self.__sum(e) - self.__sum(s) def __sum(self, pos: int): ans = 0 while pos > 0: ans += self.__data[pos - 1] pos -= pos & -pos return ans def main(): T = int(input()) for i in range(T): N = int(input()) *L, = map(int, input().split()) D = {} for i in range(N): D[L[i]] = D.get(L[i], 0) + 1 A = sorted(D.values(), reverse=True) print(min(sum(A)//3, sum(A[1:])//2, sum(A[2:]))) if __name__ == '__main__': main()