8879 | 2024. 02. 02 18:34:34 | NagyLeo | Legmesszebbi rossz sorrendű (35 pont) | python3 | Elfogadva 35/35 | 123ms | 36692 KiB |
def find_misplaced_elements(nums, n):
max_length = 0
first_num = 0
second_num = 0
minimums = [0] * n
# minimums[-i] megmondja a leghatso i minimumat
minimums[-1] = nums[-1]
for i in range(n - 2, -1, -1):
minimums[i] = min(minimums[i + 1], nums[i])
for i in range(n - 1):
# if minimums[i+1] >= nums[i]:
# continue
if minimums[-1] < nums[i]:
if n - 1 - i > max_length:
max_length = n - 1 - i
first_num = i
second_num = n - 1
continue
lo = max_length + i + 1
if lo > n - 1:
break
hi = n - 1
if minimums[lo] >= nums[i]:
continue
while hi - lo > 1:
mid = (lo + hi) // 2
if minimums[mid] < nums[i]:
lo = mid
else:
hi = mid
max_length = lo - i
first_num = i
second_num = lo
if max_length > 0:
print(first_num + 1, second_num + 1)
else:
print(-1)
n = int(input())
nums = list(map(int, input().split()))
n = len(nums)
find_misplaced_elements(nums, n)
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 35/35 | ||||||
1 | Elfogadva | 0/0 | 17ms | 11252 KiB | |||
2 | Elfogadva | 0/0 | 116ms | 34636 KiB | |||
3 | Elfogadva | 1/1 | 17ms | 11860 KiB | |||
4 | Elfogadva | 1/1 | 17ms | 11496 KiB | |||
5 | Elfogadva | 1/1 | 17ms | 11932 KiB | |||
6 | Elfogadva | 1/1 | 17ms | 11896 KiB | |||
7 | Elfogadva | 1/1 | 17ms | 12376 KiB | |||
8 | Elfogadva | 1/1 | 18ms | 12608 KiB | |||
9 | Elfogadva | 1/1 | 19ms | 12928 KiB | |||
10 | Elfogadva | 1/1 | 20ms | 13408 KiB | |||
11 | Elfogadva | 1/1 | 21ms | 13556 KiB | |||
12 | Elfogadva | 2/2 | 59ms | 21960 KiB | |||
13 | Elfogadva | 2/2 | 64ms | 23008 KiB | |||
14 | Elfogadva | 2/2 | 68ms | 23576 KiB | |||
15 | Elfogadva | 2/2 | 48ms | 19380 KiB | |||
16 | Elfogadva | 2/2 | 68ms | 24044 KiB | |||
17 | Elfogadva | 2/2 | 86ms | 28296 KiB | |||
18 | Elfogadva | 2/2 | 97ms | 30324 KiB | |||
19 | Elfogadva | 2/2 | 104ms | 32592 KiB | |||
20 | Elfogadva | 2/2 | 109ms | 34872 KiB | |||
21 | Elfogadva | 2/2 | 116ms | 36692 KiB | |||
22 | Elfogadva | 2/2 | 118ms | 36520 KiB | |||
23 | Elfogadva | 2/2 | 120ms | 36444 KiB | |||
24 | Elfogadva | 2/2 | 123ms | 36676 KiB |