結果
問題 | No.2089 置換の符号 |
ユーザー | SidewaysOwl |
提出日時 | 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()) + 1self.arr = [mono] * self.sizeself.calc = calcself.mono = monodef update(self,i,val):while i < self.size:self.arr[i] = self.calc([self.arr[i],val])i += -i & idef query(self,i):res = self.monowhile i > 0:res = self.calc([res,self.arr[i]])i -= -i & ireturn resbit = BIT(n+1,sum,0)cnt = 0for 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)