結果
問題 | No.2089 置換の符号 |
ユーザー |
![]() |
提出日時 | 2022-09-30 21:49:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 697 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 76,928 KB |
最終ジャッジ日時 | 2024-12-22 23:17:05 |
合計ジャッジ時間 | 2,834 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
n = int(input()) s = list(map(int,input().split())) class BIT(): def __init__(self,n,calc,mono): self.size = (1 << (n-1).bit_length()) + 1 self.arr = [mono] * self.size self.calc = calc self.mono = mono def update(self,i,val): while i < self.size: self.arr[i] = self.calc([self.arr[i],val]) i += -i & i def query(self,i): res = self.mono while i > 0: res = self.calc([res,self.arr[i]]) i -= -i & i return res bit = BIT(n+1,sum,0) cnt = 0 for i in range(n): cnt += bit.query(s[-(i+1)]) bit.update(s[-(i+1)]+1,1) if cnt & 1: print(-1) else: print(1)