結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-12-01 04:50:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 388 ms / 2,000 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 264,156 KB |
最終ジャッジ日時 | 2024-11-21 04:13:49 |
合計ジャッジ時間 | 10,983 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import sysinput = sys.stdin.readlineN,L,R=map(int,input().split())A=list(map(int,input().split()))ANS=[-1]*62for i in range(1,N):if A[i]==A[i-1]:print(0)sys.exit()for i in range(61,-1,-1):B=[a>>i for a in A]C=[b^1 for b in B]flagb=1flagc=1for j in range(1,N):if B[j-1]>B[j]:flagb=0if C[j-1]>C[j]:flagc=0if flagb and flagc:ANS[i]=2elif flagb:ANS[i]=0elif flagc:ANS[i]=1A=[a^(1<<i) for a in A]else:print(0)sys.exit()def calc(N,keta):if N<0:return 0if keta==-1:return 1if N & (1<<keta)==0:if ANS[keta]==0:return calc(N,keta-1)elif ANS[keta]==1:return 0elif ANS[keta]==2:return calc(N,keta-1)else:if ANS[keta]==0:return 1<<(ANS[:keta].count(2))elif ANS[keta]==1:return calc(N,keta-1)elif ANS[keta]==2:return calc(N,keta-1)+(1<<(ANS[:keta].count(2)))print(calc(R,60)-calc(L-1,60))