結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2021-01-22 17:56:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,228 ms / 2,000 ms |
コード長 | 1,664 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 157,756 KB |
最終ジャッジ日時 | 2024-12-27 07:02:28 |
合計ジャッジ時間 | 29,303 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
N, L, R = map(int, input().split())A = list(map(int, input().split()))U = 62bit = [3] * Udef dfs(d, A):if d < 0:returna0 = []a1 = []c01 = 0c10 = 0for i, a in enumerate(A):now = (a >> d) & 1if now:a1.append(a)else:a0.append(a)if i == 0:pre = nowcontinueif pre == 0 and now == 1:c01 += 1if pre == 1 and now == 0:c10 += 1pre = nowpair = (c01, c10)if pair == (0, 0):bit[d] &= 3elif pair == (0, 1):bit[d] &= 2elif pair == (1, 0):bit[d] &= 1else:bit[d] &= 0if a0:dfs(d - 1, a0)if a1:dfs(d - 1, a1)dfs(U - 1, A)dp = [[[0] * 2 for _ in range(2)] for _ in range(U + 1)]dp[0][0][0] = 1for i in range(U):shift = U-i-1D = bit[shift]Rbit = (R >> shift) & 1Lbit = (L >> shift) & 1for j in range(2):for k in range(2):for d in range(2):if (D >> d) & 1:ni = i + 1nj = jnk = kif nj == 0:if d < Rbit:nj = 1if d > Rbit:continueif nk == 0:if d > Lbit:nk = 1if d < Lbit:continuedp[ni][nj][nk] += dp[i][j][k]ans = 0for j in range(2):for k in range(2):ans += dp[U][j][k]print(ans)