結果
問題 | No.1209 XOR Into You |
ユーザー |
|
提出日時 | 2020-08-30 14:50:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 1,115 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 116,356 KB |
最終ジャッジ日時 | 2024-11-15 07:57:47 |
合計ジャッジ時間 | 8,289 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
class BIT():def __init__(self,n):self.BIT=[0]*(n+1)self.num=ndef query(self,idx):res_sum = 0while idx > 0:res_sum += self.BIT[idx]idx -= idx&(-idx)return res_sum#Ai += x O(logN)def update(self,idx,x):while idx <= self.num:self.BIT[idx] += xidx += idx&(-idx)returnN=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))dA=[A[i] for i in range(N)]for i in range(1,N):dA[i]=A[i]^A[i-1]dB=[B[i] for i in range(N)]for i in range(1,N):dB[i]=B[i]^B[i-1]id=1dic={}for b in dB:if b not in dic:dic[b]=[]dic[b].append(id)id+=1for b in dic:dic[b]=dic[b][::-1]convertA=[-1 for i in range(N)]for i in range(N):a=dA[i]if a not in dic:exit(print(-1))if not dic[a]:exit(print(-1))convertA[i]=dic[a].pop()#print(convertA)if convertA[0]!=1:exit(print(-1))res=0bit=BIT(N)for i in range(N):res+=i-bit.query(convertA[i])bit.update(convertA[i],1)print(res)