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

@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 минут
ладно ща тогда заведу отдельную тему

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@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

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

Решение