Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import bisect
- def findMinimumTime(password: str, attackOrder: list[int], m: int) -> int:
- N = len(password)
- if N == 0:
- return 0
- if m == 0:
- return 1
- def count_substrings_from_length(k: int) -> int:
- if k <= 0:
- return 0
- return k * (k + 1) // 2
- malicious_sites_sorted = [-1, N]
- current_total_clean_substrings = count_substrings_from_length(N)
- total_possible_substrings = current_total_clean_substrings
- for t, attack_pos_1_indexed in enumerate(attackOrder):
- time_step = t + 1
- attack_idx_0_based = attack_pos_1_indexed - 1
- insertion_idx = bisect.bisect_left(malicious_sites_sorted, attack_idx_0_based)
- prev_mal_idx = malicious_sites_sorted[insertion_idx - 1]
- next_mal_idx = malicious_sites_sorted[insertion_idx]
- len_old_segment = next_mal_idx - prev_mal_idx - 1
- current_total_clean_substrings -= count_substrings_from_length(len_old_segment)
- len_left_segment = attack_idx_0_based - prev_mal_idx - 1
- current_total_clean_substrings += count_substrings_from_length(len_left_segment)
- len_right_segment = next_mal_idx - attack_idx_0_based - 1
- current_total_clean_substrings += count_substrings_from_length(len_right_segment)
- malicious_sites_sorted.insert(insertion_idx, attack_idx_0_based)
- num_malicious_substrings = total_possible_substrings - current_total_clean_substrings
- if num_malicious_substrings >= m:
- return time_step
- return -1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
