結果
問題 | No.696 square1001 and Permutation 5 |
ユーザー |
|
提出日時 | 2023-06-13 19:53:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 689 ms / 10,000 ms |
コード長 | 1,541 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 102,364 KB |
最終ジャッジ日時 | 2024-06-22 05:48:03 |
合計ジャッジ時間 | 3,836 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
import syssys.set_int_max_str_digits(1000000)N = int(input())P = tuple(map(int, input().split()))class BIT():def __init__(self, sequence):self.size = len(sequence)self.depth = self.size.bit_length()self.build(sequence)def build(self, sequence):data = sequencesize = self.sizefor I, X in enumerate(data):J = I + (I & (-I))if J < size:data[J] += data[I]self.data = datadef SUM(self, I):data = self.dataS = 0while I:S += data[I]I -= I & -Ireturn Sdef ADD(self, I, X):data = self.datasize = self.sizewhile I < size:data[I] += XI += I & -Idef FIND(self, K):data = self.datasize = self.sizeX, SX = 0, 0DX = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):DX = (1 << i)if X + DX >= size:continueY = X + DXSY = SX + data[Y]if SY < K:X, SX = Y, SYreturn X + 1bit, g = BIT([0] * (N + 1)), [0] * Nfor I, X in enumerate(P):g[I] = X - 1 - bit.SUM(X)bit.ADD(X, 1)NUMS, COES = g[::-1], list(range(1, N + 1))while True:N = len(NUMS)if N == 1:breakfor i in range(1, N, 2):NUMS[i - 1] += COES[i - 1] * NUMS[i]COES[i - 1] *= COES[i]NUMS = NUMS[::2]COES = COES[::2]print(NUMS[0] + 1)