結果
問題 | No.1240 Or Sum of Xor Pair |
ユーザー | chineristAC |
提出日時 | 2020-08-25 02:01:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 950 ms / 2,000 ms |
コード長 | 2,036 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 86,636 KB |
実行使用メモリ | 109,364 KB |
最終ジャッジ日時 | 2023-09-04 07:56:43 |
合計ジャッジ時間 | 24,025 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 255 ms
79,508 KB |
testcase_01 | AC | 251 ms
79,624 KB |
testcase_02 | AC | 688 ms
79,744 KB |
testcase_03 | AC | 650 ms
80,332 KB |
testcase_04 | AC | 745 ms
80,044 KB |
testcase_05 | AC | 737 ms
79,980 KB |
testcase_06 | AC | 766 ms
80,076 KB |
testcase_07 | AC | 590 ms
80,112 KB |
testcase_08 | AC | 752 ms
80,292 KB |
testcase_09 | AC | 691 ms
80,416 KB |
testcase_10 | AC | 791 ms
81,572 KB |
testcase_11 | AC | 693 ms
81,976 KB |
testcase_12 | AC | 710 ms
83,160 KB |
testcase_13 | AC | 633 ms
83,164 KB |
testcase_14 | AC | 673 ms
83,456 KB |
testcase_15 | AC | 679 ms
109,072 KB |
testcase_16 | AC | 747 ms
109,348 KB |
testcase_17 | AC | 390 ms
109,116 KB |
testcase_18 | AC | 706 ms
109,156 KB |
testcase_19 | AC | 830 ms
108,924 KB |
testcase_20 | AC | 832 ms
109,196 KB |
testcase_21 | AC | 728 ms
109,308 KB |
testcase_22 | AC | 776 ms
109,192 KB |
testcase_23 | AC | 841 ms
108,840 KB |
testcase_24 | AC | 907 ms
109,100 KB |
testcase_25 | AC | 802 ms
109,076 KB |
testcase_26 | AC | 950 ms
109,144 KB |
testcase_27 | AC | 273 ms
79,712 KB |
testcase_28 | AC | 309 ms
79,480 KB |
testcase_29 | AC | 189 ms
109,364 KB |
testcase_30 | AC | 749 ms
94,644 KB |
testcase_31 | AC | 824 ms
95,824 KB |
testcase_32 | AC | 739 ms
109,140 KB |
ソースコード
import sys,random input=sys.stdin.readline N,X=map(int,input().split()) A=list(map(int,input().split())) def solve_square(): a,b=X//512,X%512 data_conv = [[0 for j in range(512)] for i in range(512)] data_bit = [[0 for j in range(9)] for i in range(512)] cnt = [0 for i in range(512)] for i in range(N): x,y = A[i]//512 , A[i]%512 data_conv[x][y] += 1 cnt[x] += 1 for j in range(9): if not y>>j & 1: data_bit[x][j] += 1 def all_sum(x,y): res = 0 upper_bit = (x | y) << 9 res += upper_bit * cnt[x] * cnt[y] for i in range(9): res += (1 << i) * (cnt[x] * cnt[y] - data_bit[x][i] * data_bit[y][i]) return res def convolute(x,y): res = 0 upper_bit = (x | y) << 9 for i in range(512): for j in range(512): if i^j < b: res += (upper_bit + (i | j)) * data_conv[x][i] * data_conv[y][j] return res def all_sum_equal(x): res = 0 upper_bit = x << 9 res += upper_bit * cnt[x] * (cnt[x] - 1) // 2 for i in range(9): res += (1 << i) * (cnt[x] * (cnt[x] - 1) // 2 - (data_bit[x][i] * (data_bit[x][i] - 1) // 2)) return res def convolute_equal(x): res = 0 upper_bit = x << 9 for i in range(512): for j in range(i): if i^j < b: res += (upper_bit + (i | j)) * data_conv[x][i] * data_conv[x][j] for i in range(512): res += (upper_bit + i) * data_conv[x][i] * (data_conv[x][i] - 1) // 2 return res ans=0 for i in range(512): for j in range(i): if i^j < a: ans += all_sum(i,j) elif i^j == a: ans += convolute(i,j) for i in range(512): if 0 < a: ans += all_sum_equal(i) elif 0 == a: ans += convolute_equal(i) return ans print(solve_square())