結果

問題 No.696 square1001 and Permutation 5
ユーザー qwewe
提出日時 2025-05-14 13:15:02
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,212 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 265,288 KB
最終ジャッジ日時 2025-05-14 13:16:21
合計ジャッジ時間 20,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Use fast I/O
input = sys.stdin.readline

def solve():
    # Read input N
    N = int(input())
    # Read the permutation p as a list of integers
    p = list(map(int, input().split()))

    # Initialize a Fenwick tree (Binary Indexed Tree, BIT).
    # The BIT will be used to keep track of available numbers.
    # It is 1-based indexed, so its size is N+1.
    bit = [0] * (N + 1)

    def update(idx, delta):
        """
        Updates the value at index idx in the BIT by delta.
        This operation takes O(log N) time.
        """
        # Iterate through idx and all ancestors in the BIT structure
        while idx <= N:
            bit[idx] += delta
            # Move to the next index responsible for idx.
            # This is done by adding the least significant bit (LSB) of idx.
            idx += idx & (-idx) 

    def query(idx):
        """
        Queries the prefix sum up to index idx in the BIT.
        This returns the sum of values from index 1 to idx.
        This operation takes O(log N) time.
        """
        # If idx is 0 or negative, the sum is 0.
        if idx <= 0:
             return 0
        
        s = 0
        # Iterate through idx and all indices it's responsible for
        while idx > 0:
            s += bit[idx]
            # Move to the 'parent' index in the BIT structure.
            # This is done by subtracting the least significant bit (LSB) of idx.
            idx -= idx & (-idx)
        return s

    # Initialize the BIT. Initially, all numbers from 1 to N are available.
    # We represent availability by setting the count for each number to 1.
    # This loop performs N updates, so initialization takes O(N log N) time.
    for i in range(1, N + 1):
        update(i, 1)

    # Variable to store the calculated 0-based rank.
    # We use Python's arbitrary precision integers, as the rank can be very large.
    rank_val = 0 
    
    # Iterate through the permutation elements from left to right (position i=1 to N).
    for i in range(1, N + 1):
        # Get the element p_i at the current position i.
        # Since the list p is 0-indexed, we access p[i-1].
        current_p = p[i-1] 
        
        # Calculate k_i: the count of available numbers strictly less than current_p.
        # Available numbers are those whose count in the BIT is 1.
        # The query(current_p - 1) gives the sum of counts for numbers from 1 to current_p - 1.
        # Since available numbers have count 1 and used numbers have count 0, this sum is exactly k_i.
        k_i = query(current_p - 1)
        
        # Update the rank using the factoradic representation logic.
        # We use a Horner-like scheme to avoid computing large factorials explicitly.
        # This scheme computes R = (...((k_1*(N-1) + k_2)*(N-2) + k_3)...)*1 + k_N
        # which is equivalent to Sum_{i=1..N} k_i * (N-i)!
        
        # If it's the first element (i=1), the rank_val is initialized with k_1.
        if i == 1:
            rank_val = k_i
        else:
            # For subsequent elements (i > 1), apply the Horner update rule:
            # rank_val = current_rank_val * (N - i + 1) + k_i
            # The multiplier (N - i + 1) corresponds to the factorial base at this position.
            # Example: for i=2, we need k_1*(N-1)! + k_2*(N-2)! + ...
            # The value from previous step is k_1. It needs to be multiplied by (N-1).
            # (N - i + 1) for i=2 is (N - 2 + 1) = N-1. This is correct.
            # For i=3, previous rank_val is k_1*(N-1) + k_2. Need to multiply by (N-2).
            # (N - i + 1) for i=3 is (N - 3 + 1) = N-2. This is correct.
            rank_val = rank_val * (N - i + 1) + k_i

        # Mark the current element current_p as used (unavailable) for future steps.
        # This is done by decreasing its count in the BIT to 0.
        # We perform update(current_p, -1).
        update(current_p, -1)

    # The problem asks for the 1-based lexicographical rank.
    # Our computed rank_val is the count of permutations strictly smaller than p (0-based rank).
    # So, we add 1 to get the final answer.
    print(rank_val + 1)

# Execute the solve function to run the program
solve()
0