Случайный массив

@WAW123 · Регистрация: 04.01.2023

Студворк — интернет-сервис помощи студентам

Есть такая задача:
ограничение по времени на тест:0.5 секунд
ограничение по памяти на тест:256 мегабайт
Входные данные
Первая строка содержит целое число n
вторая — n
случайных целых чисел ai
(1≤ai≤n≤2^18).
Выходные данные
Выведите n строк: k-я строка должна содержать два целых числа i и j таких, что |ai−aj|=k.Если таких позиций не существует, оба числа должны быть равны нулю.
есть решение за O(n^2):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    c=0
    for j in range(n):
        if a[j]+i in a:
            print(j+1,a.index(a[j]+i)+1)
            c=1
            break
        elif a[j]-i in a:
            print(a.index(a[j]-i)+1,j+1)
            c=1
            break
    if c==0:
        print(0,0)

Но для n≤2^18 надо выполнять вероятно за O(n).поможете с этой задачей, пожалуйста.

Добавлено через 34 минуты
вот один из примеров:
входные данные
10
2 10 4 1 5 9 3 2 4 2
выходные данные
9 7
9 10
8 5
5 4
5 2
6 7
6 10
2 10
4 2
0 0

@eaa · 27.03.2023, 17:06

Сообщение от WAW123

n≤2^18

да же для c++ за 0,5 сек это не решаемо за O(n)

Добавлено через 1 минуту
сорри, думал 10^18. тогда все решаемо.

@WAW123 · 27.03.2023, 17:08 **[ТС]**

тогда выходит за O(logn) надо решить?

Добавлено через 2 минуты
но как?Можете просто подсказать.Я сам сегодня весь день мучался и ток за O(n^2).Просто я стараюсь сам решать задачи.И если я прошу помощи,то самое лучшее это подсказка.А то если мне сразу скажут решение,то у меня в голове ничего не останится

@eaa · 27.03.2023, 17:14

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    c=0
    for j in range(n):
        if a[j]+i in a: # заменить на O(1) или O(log(n))
            print(j+1,a.index(a[j]+i)+1) # заменить на O(1) или O(log(n))
            c=1
            break
        elif a[j]-i in a: # заменить на O(1) или O(log(n))
            print(a.index(a[j]-i)+1,j+1) # заменить на O(1) или O(log(n))
            c=1
            break
    if c==0:
        print(0,0)

Добавлено через 3 минуты
тогда будет O(n^2). у тебя вообще O(n^3)

@WAW123 · 28.03.2023, 08:59 **[ТС]**

eaa, вот:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n=int(input())
a=list(map(int,input().split()))
m=dict.fromkeys(a,0)
for i in range(n):
    m[a[i]]=i+1
for i in range(1,n+1):
    c=0
    for j in range(n):
        if a[j]+i in m:
            print(j+1,m[a[j]+i])
            c=1
            break
        elif a[j]-i in m:
            print(m[a[j]-i],j+1)
            c=1
            break
    if c==0:
        print(0,0)

Добавлено через 29 секунд
но это решение не проходит последнюю группу тестов,где 2^17<=n<=2^18.

Добавлено через 1 минуту
вероятно надо за O(n).вы не подскажите как за O(n)?

@iSmokeJC · 28.03.2023, 09:08

Сообщение от WAW123

как за O(n)?

Да никак

@WAW123 · 28.03.2023, 10:05 **[ТС]**

iSmokeJC, а может тогда это решение усовершенствовать как-нибудь?

Добавлено через 48 минут
или перевести это решение с питон на c++.Как раз на c++ есть такой же быстрый словарь как dict в питон-unordered_map.

@WAW123 · 28.03.2023, 20:15 **[ТС]**

ребят,поможете с переводом с питон на c++ вот этого кода:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n=int(input())
a=list(map(int,input().split()))
m=dict.fromkeys(a,0)
for i in range(n):
    m[a[i]]=i+1
for i in range(1,n+1):
    c=0
    for j in range(n):
        if a[j]+i in m:
            print(j+1,m[a[j]+i])
            c=1
            break
        elif a[j]-i in m:
            print(m[a[j]-i],j+1)
            c=1
            break
    if c==0:
        print(0,0)

У меня с c++ всё плохо

Добавлено через 50 минут
ладно ща тогда заведу отдельную тему

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: показать затраченные материалы за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@WAW123 0 / 0 / 0 Регистрация: 04.01.2023 Сообщений: 31
	27.03.2023, 17:08 [ТС]
	тогда выходит за O(logn) надо решить? Добавлено через 2 минуты но как?Можете просто подсказать.Я сам сегодня весь день мучался и ток за O(n^2).Просто я стараюсь сам решать задачи.И если я прошу помощи,то самое лучшее это подсказка.А то если мне сразу скажут решение,то у меня в голове ничего не останится 0

@WAW123 0 / 0 / 0 Регистрация: 04.01.2023 Сообщений: 31
	28.03.2023, 10:05 [ТС]
	iSmokeJC, а может тогда это решение усовершенствовать как-нибудь? Добавлено через 48 минут или перевести это решение с питон на c++.Как раз на c++ есть такой же быстрый словарь как dict в питон-unordered_map. 0

Опции темы

Случайный массив

Решение