結果
問題 | No.1240 Or Sum of Xor Pair |
ユーザー | chineristAC |
提出日時 | 2020-08-25 14:37:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 583 ms / 2,000 ms |
コード長 | 2,042 bytes |
コンパイル時間 | 437 ms |
コンパイル使用メモリ | 86,428 KB |
実行使用メモリ | 109,688 KB |
最終ジャッジ日時 | 2023-09-04 07:41:59 |
合計ジャッジ時間 | 18,193 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 195 ms
79,704 KB |
testcase_01 | AC | 191 ms
79,796 KB |
testcase_02 | AC | 345 ms
79,704 KB |
testcase_03 | AC | 503 ms
80,584 KB |
testcase_04 | AC | 526 ms
80,324 KB |
testcase_05 | AC | 502 ms
80,392 KB |
testcase_06 | AC | 436 ms
80,172 KB |
testcase_07 | AC | 432 ms
80,356 KB |
testcase_08 | AC | 440 ms
80,152 KB |
testcase_09 | AC | 430 ms
80,352 KB |
testcase_10 | AC | 460 ms
81,652 KB |
testcase_11 | AC | 533 ms
82,376 KB |
testcase_12 | AC | 455 ms
83,840 KB |
testcase_13 | AC | 494 ms
83,276 KB |
testcase_14 | AC | 507 ms
84,012 KB |
testcase_15 | AC | 529 ms
109,348 KB |
testcase_16 | AC | 573 ms
109,476 KB |
testcase_17 | AC | 399 ms
109,688 KB |
testcase_18 | AC | 538 ms
109,252 KB |
testcase_19 | AC | 384 ms
109,240 KB |
testcase_20 | AC | 401 ms
109,404 KB |
testcase_21 | AC | 548 ms
109,244 KB |
testcase_22 | AC | 578 ms
109,344 KB |
testcase_23 | AC | 387 ms
109,240 KB |
testcase_24 | AC | 577 ms
109,272 KB |
testcase_25 | AC | 572 ms
109,272 KB |
testcase_26 | AC | 583 ms
109,480 KB |
testcase_27 | AC | 212 ms
79,620 KB |
testcase_28 | AC | 248 ms
79,760 KB |
testcase_29 | AC | 263 ms
109,412 KB |
testcase_30 | AC | 497 ms
95,000 KB |
testcase_31 | AC | 433 ms
95,980 KB |
testcase_32 | AC | 536 ms
109,324 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//256,X%256 data_conv = [[0 for j in range(256)] for i in range(1024)] data_bit = [[0 for j in range(8)] for i in range(1024)] cnt = [0 for i in range(1024)] for i in range(N): x,y = A[i]//256 , A[i]%256 data_conv[x][y] += 1 cnt[x] += 1 for j in range(8): if not y>>j & 1: data_bit[x][j] += 1 def all_sum(x,y): res = 0 upper_bit = (x | y) << 8 res += upper_bit * cnt[x] * cnt[y] for i in range(8): 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) << 8 for i in range(256): for j in range(256): 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 << 8 res += upper_bit * cnt[x] * (cnt[x] - 1) // 2 for i in range(8): 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 << 8 for i in range(256): 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(256): res += (upper_bit + i) * data_conv[x][i] * (data_conv[x][i] - 1) // 2 return res ans=0 for i in range(1024): 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(1024): if 0 < a: ans += all_sum_equal(i) elif 0 == a: ans += convolute_equal(i) return ans print(solve_square())