Submission #9228535


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,readline().split())
A = np.array(read().split(),np.int64)

f = np.bincount(A)

fft_len = 1<<18
fft = np.fft.rfft; ifft = np.fft.irfft
Ff = fft(f,fft_len)
G = np.rint(ifft(Ff * Ff,fft_len)).astype(np.int64) # 和 -> 何通りか

Gcum = G.cumsum()
remove_cnt = N * N - M
i = np.searchsorted(Gcum,remove_cnt)

# i未満は全部除外。ちょうどiのものもいくつか除外
x = remove_cnt - Gcum[i-1]
remove_sum = (G[:i] * np.arange(i,dtype=np.int64)).sum() + i * x

answer = A.sum() * 2 * N - remove_sum
print(answer)

Submission Info

Submission Time
Task E - Handshake
User maspy
Language Python (3.4.3)
Score 500
Code Size 700 Byte
Status AC
Exec Time 192 ms
Memory 30976 KB

Judge Result

Set Name Sample All after_contest
Score / Max Score 0 / 0 500 / 500 0 / 0
Status
AC × 3
AC × 66
AC
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 100.txt, 101.txt, 102.txt, 103.txt, 104.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, s1.txt, s2.txt, s3.txt
after_contest
Case Name Status Exec Time Memory
01.txt AC 174 ms 28512 KB
02.txt AC 172 ms 27104 KB
03.txt AC 172 ms 27360 KB
06.txt AC 173 ms 27852 KB
07.txt AC 189 ms 30028 KB
08.txt AC 181 ms 28584 KB
09.txt AC 182 ms 28632 KB
10.txt AC 175 ms 27868 KB
100.txt AC 174 ms 27828 KB
101.txt AC 173 ms 27376 KB
102.txt AC 173 ms 27076 KB
103.txt AC 173 ms 28060 KB
104.txt AC 172 ms 28768 KB
11.txt AC 188 ms 28936 KB
12.txt AC 178 ms 28728 KB
13.txt AC 190 ms 29472 KB
14.txt AC 190 ms 29964 KB
15.txt AC 191 ms 30356 KB
16.txt AC 190 ms 30704 KB
17.txt AC 191 ms 30556 KB
18.txt AC 191 ms 30376 KB
19.txt AC 192 ms 30036 KB
20.txt AC 192 ms 29316 KB
21.txt AC 191 ms 29376 KB
22.txt AC 192 ms 29156 KB
23.txt AC 191 ms 30352 KB
24.txt AC 190 ms 28864 KB
25.txt AC 191 ms 29224 KB
26.txt AC 190 ms 29404 KB
27.txt AC 191 ms 30600 KB
28.txt AC 192 ms 30828 KB
29.txt AC 190 ms 29240 KB
30.txt AC 190 ms 30976 KB
31.txt AC 188 ms 28520 KB
32.txt AC 189 ms 28940 KB
33.txt AC 189 ms 27904 KB
34.txt AC 188 ms 28112 KB
35.txt AC 188 ms 27568 KB
36.txt AC 189 ms 27844 KB
37.txt AC 190 ms 29768 KB
38.txt AC 190 ms 28280 KB
39.txt AC 190 ms 28768 KB
40.txt AC 190 ms 28840 KB
41.txt AC 190 ms 29120 KB
42.txt AC 190 ms 29624 KB
43.txt AC 188 ms 28236 KB
44.txt AC 190 ms 29136 KB
45.txt AC 188 ms 28792 KB
46.txt AC 188 ms 28312 KB
47.txt AC 189 ms 29996 KB
48.txt AC 188 ms 28284 KB
49.txt AC 190 ms 28124 KB
50.txt AC 190 ms 28412 KB
51.txt AC 191 ms 27604 KB
52.txt AC 190 ms 28544 KB
53.txt AC 189 ms 28252 KB
54.txt AC 190 ms 28204 KB
55.txt AC 191 ms 29212 KB
56.txt AC 188 ms 27588 KB
57.txt AC 190 ms 29656 KB
58.txt AC 185 ms 27724 KB
59.txt AC 192 ms 30232 KB
60.txt AC 190 ms 27928 KB
s1.txt AC 172 ms 27872 KB
s2.txt AC 172 ms 26976 KB
s3.txt AC 173 ms 28812 KB