Как ускорить код? Оптимизировать?

@DOPIXKMNLD · Регистрация: 17.10.2022

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N, K, Q = map(int, input().split())
perm = list(range(1, N + 1))
 
for _ in range(K):
    k = int(input())
    block_len = 1 << k
    new_perm = [0] * N
    for i in range(0, N, block_len * 2):
        new_perm[i + block_len : i + block_len * 2] = perm[i : i + block_len]
        new_perm[i : i + block_len] = perm[i + block_len : i + block_len * 2]
    perm = new_perm
 
for _ in range(Q):
    q = int(input())
    print(perm[q - 1])

Насчет задачи напишу в ЛС

nikulinn_artyomm · 27.08.2023, 18:02

Я вам ЛС написал.
У меня примерно так получилось.

Python
1
2
3
4
5
6
7
8
9
10
N, K, Q = map(int, input().split())
perm = list(range(1, N + 1))
 
for k in map(int, input().split()):
    block_len = 1 << k
    for i in range(0, N, block_len * 2):
        perm[i + block_len : i + block_len * 2], perm[i : i + block_len] = perm[i : i + block_len], perm[i + block_len : i + block_len * 2]
 
for q in map(int, input().split()):
    print(perm[q - 1])

@eaa · 30.08.2023, 09:55

DOPIXKMNLD, а задача какая?
понял что даны какие то N и К. и нужно ответить на Q запросов.
видимо из серии Дерево отрезков, Дерево Фенвика и т.п.

@DOPIXKMNLD · 30.08.2023, 10:05 **[ТС]**

eaa, уже решил, на питоне тл выскаивал постоянно, а на с++ зашло

Добавлено через 2 минуты
У вас есть перестановка из элементов, с общим числом 2 в степени i. По заданному числу h, 0<=h<=i, нужно разложить перестановку на блоки длиной 2^i, которые обязательно не пересекаются. Т.е. 1-й блок - (1 ... 2^h), 2 - (2^h+1, ..., 2*2^h), 3 - (2^h*2+1, ..., 3*2^h), и т.д. Далее соседние блоки свайпнуть. Т.е. 1-й со 2-м, 3-й с 4-м и т.д.

Дан набор позиций, нужно определить, какие элементы будут находиться на этих позициях после выполнения всех операций.

Вводятся A = 2^i, B>=1, C<=100000, --- кол-во элементов в перестановке, кол-во операций и кол-во интересующих позиций, соответсвенно
Далее следуют B строк, в каждой из которых содержится одно число hj (0 ≤ hj < i), означающие, что нужно менять соседние блоки по 2^hj элементов
Затем следуют C строк, в каждой из которых содержится одно число cj (1 ≤ cj ≤ A), представляющее интересующую позицию.
Формат вывода: Вывести C строк, в j-й строке указать номер элемента перестановки на позиции cj.
Пример:
Входные данные
9 3 3
1
2
5
4
2
5

Результат работы
6
8
3

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.08.2023, 09:55
	DOPIXKMNLD, а задача какая? понял что даны какие то N и К. и нужно ответить на Q запросов. видимо из серии Дерево отрезков, Дерево Фенвика и т.п. 0

@DOPIXKMNLD Йуный плагиат-падаван) 176 / 119 / 45 Регистрация: 17.10.2022 Сообщений: 566
	30.08.2023, 10:05 [ТС]
	eaa, уже решил, на питоне тл выскаивал постоянно, а на с++ зашло Добавлено через 2 минуты У вас есть перестановка из элементов, с общим числом 2 в степени i. По заданному числу h, 0<=h<=i, нужно разложить перестановку на блоки длиной 2^i, которые обязательно не пересекаются. Т.е. 1-й блок - (1 ... 2^h), 2 - (2^h+1, ..., 22^h), 3 - (2^h2+1, ..., 3*2^h), и т.д. Далее соседние блоки свайпнуть. Т.е. 1-й со 2-м, 3-й с 4-м и т.д. Дан набор позиций, нужно определить, какие элементы будут находиться на этих позициях после выполнения всех операций. Вводятся A = 2^i, B>=1, C<=100000, --- кол-во элементов в перестановке, кол-во операций и кол-во интересующих позиций, соответсвенно Далее следуют B строк, в каждой из которых содержится одно число hj (0 ≤ hj < i), означающие, что нужно менять соседние блоки по 2^hj элементов Затем следуют C строк, в каждой из которых содержится одно число cj (1 ≤ cj ≤ A), представляющее интересующую позицию. Формат вывода: Вывести C строк, в j-й строке указать номер элемента перестановки на позиции cj. Пример: Входные данные 9 3 3 1 2 5 4 2 5 Результат работы 6 8 3 0

Как ускорить код? Оптимизировать?

Решение