Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566

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

27.08.2023, 15:16. Показов 4118. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    long long N, K, Q;
    cin >> N >> K >> Q;
    
    vector<int> perm(N);
    for (long long i = 0; i < N; ++i) {
        perm[i] = i + 1;
    }
 
    for (long long k_iter = 0; k_iter < K; ++k_iter) {
        long long k;
        cin >> k;
        long long block_len = 1 << k;
        vector<int> new_perm(N);
        for (long long i = 0; i < N; i += block_len * 2) {
            for (long long j = 0; j < block_len; ++j) {
                new_perm[i + j + block_len] = perm[i + j];
                new_perm[i + j] = perm[i + j + block_len];
            }
        }
        perm = new_perm;
    }
 
    for (long long q_iter = 0; q_iter < Q; ++q_iter) {
        long long q;
        cin >> q;
        cout << perm[q - 1] << endl;
    }
 
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
27.08.2023, 15:16
Ответы с готовыми решениями:

Как ускорить код?
Решаю задачу на нахождение суммы в подматрице через префиксы. Написал код, но не проходит по времени. Как можно ускорить? Сначала...

Как ускорить код?
Есть код : #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;memory.h&gt; #include &lt;iostream&gt; using namespace std; const int N =...

Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода)
есть код, нужно cout и cin перевести на printf и scanf дополнительных библиотек не подключать! проблема в том что при вводе 14 работает...

36
Нарушитель
Эксперт функциональных языков программированияЭксперт С++
6318 / 3043 / 1054
Регистрация: 01.06.2021
Сообщений: 11,601
28.08.2023, 23:14
Студворк — интернет-сервис помощи студентам
SmallEvil, я так понимаю тут какой-то обмен блоками длиной 2^k между массивами perm и new_perm, причем k вводится из клавиатуры.
0
 Аватар для Наталья8
625 / 383 / 67
Регистрация: 09.03.2016
Сообщений: 4,276
28.08.2023, 23:25
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
cin >> N >> K >> Q;
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
cin >> k;
В натуре... син туда да син сюда.
Ну его на хрен. Сам ускоряй свою байду...
0
28.08.2023, 23:37

Не по теме:

Цитата Сообщение от Наталья8 Посмотреть сообщение
В натуре... син туда да син сюда.
Это специальная техника программирования - олимпиадная.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
typedef long long ll;
int i, j, l=1, lj;
 
int main()
{
    cin >> i,j;
    ll li = i + 1;
    for(i=j; li<j; li=i+l)
        ++l;
    cout << lj;
    return 0;
}
Конечно я это придумал.
А вот реальные листинги :
Найти max количество подряд идущих элементов последовательности, которые делятся на одно и то же натуральное число
Старый недобрый time limit exceeded
... их можно бесконечно искать на форуме ...

0
 Аватар для Storm Screamer
5251 / 1557 / 121
Регистрация: 21.04.2013
Сообщений: 9,113
29.08.2023, 03:54
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
проблема не решена
Какая проблема? Здесь нужно было накидать ассемблерные вставки или может тонко настроить компилятор на оптимизацию более жесткую? Внесите ясность.
0
Just Do It!
 Аватар для XLAT
4220 / 2683 / 656
Регистрация: 23.09.2014
Сообщений: 9,236
Записей в блоге: 3
29.08.2023, 04:21
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Внесите ясность.
там у него 3 вложенных фора,
что намекает на дубовый брутфорс,
а это уже подразумевает оптимизацию алгоритма,
точнее, его смену.

но так как сама задача не озвучена, то и взятки гладки...
0
 Аватар для Storm Screamer
5251 / 1557 / 121
Регистрация: 21.04.2013
Сообщений: 9,113
29.08.2023, 04:36
Цитата Сообщение от XLAT Посмотреть сообщение
что намекает на дубовый брутфорс,
Брут в один поток? Сурово.
0
Just Do It!
 Аватар для XLAT
4220 / 2683 / 656
Регистрация: 23.09.2014
Сообщений: 9,236
Записей в блоге: 3
29.08.2023, 04:47
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Сурово.
я так и написал: дубово.

Цитата Сообщение от Storm Screamer Посмотреть сообщение
в один поток?
валидатор хозяйский - вряд ли школьникам отдадут сразу все ядра на их брутфорс.
за 2 сек не уложился - иди гуляй дальше...
а много потоков на одном ядре будет ещё больше тормозить.
0
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
29.08.2023, 09:59  [ТС]
Цитата Сообщение от Royal_X Посмотреть сообщение
а вот по тому же Фрейду, если мерещатся змеи, то значит человеку хочется пениса


SmallEvil, написал, извинияюсь, что принес тебе так много сложностей, да и всем Вам

Добавлено через 2 минуты
Ладно, легче уж сюда выложить ".. распарсенную задачу"
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
29.08.2023, 10:02
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
написал, извинияюсь, что принес тебе так много сложностей, да и всем Вам
Не нужно извиняться. Просто придерживайтесь правил и обычного приличия поведения.
Никто вам ничего не подскажет без ТЗ.
0
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
29.08.2023, 10:21  [ТС]
Добавлено через 11 минут
Эм, получилось не очень, вот адекватный вариант:
У вас есть перестановка из элементов, с общим числом 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
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
29.08.2023, 12:20
Код еще нужно дотестировать...

Добавлено через 12 минут
Может у вас неверные входные данные ?
Или где то неточность в диапазоне вводимых данных. Например экспонента или еще какой.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <cstring>
using namespace std;
 
struct Block{
    char* start;
    size_t size;
};
// block size must be equal
// buf size must be not less then block
void swap_block(Block lhs, Block rhs, char* buf){
    if (lhs.start == rhs.start)
        return;
    memcpy(buf, lhs.start, lhs.size);
    memcpy(lhs.start, rhs.start, lhs.size);
    memcpy(rhs.start, buf, rhs.size);
}
int main()
{
    unsigned i_exp;             // N = 2^i
    unsigned int elements_c;    // N - количество элементов в последовательности (перестановке)
    unsigned int operations_c;  // Q - количество операций
    unsigned int positions_c;   // K - количество позиций выборки
    cin >> i_exp >> operations_c >> positions_c;
    elements_c = (1u << i_exp);
    
    vector<int> seq(elements_c);
    iota(seq.begin(), seq.end(), 1);
    
    // test sequence
    // copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, " "));
    for(size_t i = 0; i != operations_c; ++i){
        unsigned int block_size;
        cin >> block_size;
        // block size (in elements)
        // cout << "Block size : " << (1u << block_size) << " elements" << endl ;
        unsigned int blocks = elements_c / (1u << block_size);
        block_size = (1 << block_size) * sizeof(decltype(seq)::value_type);
        // cout << "Blocks : " << blocks << endl;
        char *seq_begin = reinterpret_cast<char*>(&seq[0]);
        char *buf = new char[block_size];
        for(size_t j = 0; j < blocks/2; ++j)
            swap_block(Block{seq_begin + j*2*block_size, block_size}, Block{seq_begin + (j*2+1)*block_size, block_size}, buf);
        delete [] buf;
        // test sequence after swap
        // copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, " "));
        // cout << endl;
    }
 
    for(size_t i = 0; i != positions_c; ++i){    
        unsigned int pos;
        cin >> pos;
        cout << seq[pos-1] << endl;
    }
}
На входных данных :
Code
1
2
3
4
5
6
9 2 3
1
2
4
2
5
Будут ваши :
Code
1
2
3
6
8
3
0
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
29.08.2023, 12:44  [ТС]
SmallEvil,
Да, вот верные данные:
Входные данные
8 3 3
0
1
2
1
3
7
Результат работы
8
6
2
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
29.08.2023, 13:00
DOPIXKMNLD, ну тогда всё ОК.
Комментарии к коду нужны (желательно конкретные места) ?

Добавлено через 6 минут
DOPIXKMNLD, А вот теперь можно будет подумать на другим алгоритмом, если нужно.

Добавлено через 4 минуты
DOPIXKMNLD, а теперь смотрим на ваш "рабочий код" на приведенных мной данных.
А именно :
Code
1
2
3
4
5
6
9 2 3
1
2
4
2
5
Code
1
2
malloc(): corrupted top size
Aborted (core dumped)
Упало...

Добавлено через 1 минуту
То есть там у вас UB. Как я и говорил.
0
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
29.08.2023, 13:08  [ТС]
Цитата Сообщение от SmallEvil Посмотреть сообщение
Комментарии к коду нужны (желательно конкретные места) ?
По алгоритму разберусь, тут вопросы больше по синтаксису
Цитата Сообщение от SmallEvil Посмотреть сообщение
iota(seq.begin(), seq.end(), 1);
что значит iota??
Цитата Сообщение от SmallEvil Посмотреть сообщение
elements_c = (1u << i_exp);
как работает эта строчка?

Добавлено через 1 минуту
И, в ваш код выдает ошибку выполнения на 3м тесте(посмотреть его не могу)
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
29.08.2023, 15:43
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
что значит iota??
std::iota
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
elements_c = (1u << i_exp);
как работает эта строчка?
Так же как и в вашем коде.
1u - литерал типа unsigned int со значением 1.
<< - битовый сдвиг влево.
То есть, свдигаем 1-у на i_exp битов влево.
Что эквивалентно степени двойки : 2i_exp

Добавлено через 59 секунд
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
И, в ваш код выдает ошибку выполнения на 3м тесте
Что значит "ошибка выполнения" ?

Добавлено через 4 минуты
DOPIXKMNLD, нужно смотреть на диапазон вводимых данных.
Возможно легче работать с самими позициями.
И не создавать всю последовательность.

Добавлено через 2 часа 24 минуты
Цитата Сообщение от SmallEvil Посмотреть сообщение
Возможно легче работать с самими позициями.
И не создавать всю последовательность.
Попробую расшифровать.
Берем все С позиций. Их начальные значения мы имеем.
И крутим их B раз, симулируя перестановки.
Эмпиричски :
Допустим у нас есть одна позиция, которум ми хотим узнать : K = 5
N = 16 (это уже в степени i, 2^4 ), B = 3, C = 1

16 3 1
4 (уже в степени)
8
2
5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Теперь трассируем перестановки в обратном порядке. Так если бы К было в 5-ой позиции.
Применяем к 5 позиции обмены (2 8 4):
5 + 2*(5%(2*2) <= 2 ? +1 : -1) = 5 + 2 = 7
7 + 8*(7%(8*2) <= 8 ? +1 : -1) = 7 + 8 = 7
15 + 4*(15%(4*2)<= 4 ? +1 : -1) = 15 - 4 = 11
Ki-1 = Ki + Bj*(Ki%(Bj*2)<= Bj ? +1 : -1)
Хорошо что у нас есть рабочий код для проверки
Input по условию.
Code
1
2
3
4
5
4 3 1
2
3
1
5
И так всю цепочку С.

Добавлено через 2 минуты
Сложность получится O(B * C) ?

Это всё мысли вслух.
1
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
30.08.2023, 10:06  [ТС]
Вот верный ответ:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int main() {
    int n, p, k;
    cin >> n >> p >> k;
 
    vector<int> a(n);
    for(int i = 0; i < n; i++) { 
        a[i] = i+1; 
    }
 
    vector<int> f(n, 0);
    vector<int> b;
    map<int, int> d;
 
    for(int i = 0; i < p; i++) {
        int q;
        cin >> q;
        
        if(d.count(q)) { 
            d[q]++;
        } else {
            d[q] = 1;
        }
    }
 
    for(auto it = d.begin(); it != d.end(); it++) {
        if(it->second % 2 == 1) {
            b.push_back(pow(2, it->first));
        }
    }
 
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
 
    for(int elem : b) {
        int q = elem;
        int g = 0;
        int w = 0;
 
        for(int i = 0; i < n; i++) {
            if(w == q) {
                w = 0;
                g++;
            }
            w++;
 
            if(g % 2 == 0) {
                f[i] += q;
            } else {
                f[i] -= q;
            }
        }
    }
 
    vector<int> c(n, 0);
 
    for(int i = 0; i < n; i++) {
        c[i+f[i]] = a[i];
    }
 
    for(int i = 0; i < k; i++) {
        int q;
        cin >> q;
        cout << c[q-1] << endl;
    }
 
    return 0;
}
1
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566
30.08.2023, 22:44  [ТС]
Или можно сетать
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
30.08.2023, 22:44

Как оптимизировать код?
Помогите, пожалуйста, оптимизировать код, преподаватель заставил, а я совсем не понимаю, что еще можно поменять. Само задание: ...

Как оптимизировать код?
мне нужно чтобы значения угла перебирались от начального до конечного в зависимости от времени, выдает ошибку, как сделать правильно...

Как оптимизировать код
Доброй ночи господа у меня к вам такая просьба как можно упростить данный код? #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

Как оптимизировать код?
Добрый день! У меня есть одна задача, решение к которой, само по себе, у меня уже есть. Однако на последнем тесте программа выполняется...

Как оптимизировать код?
Написал программу, которая считает время, проведённое за компьютером. Каким образом её можно оптимизировать? Как улучшить качество кода? ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Опции темы

Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru