Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.83/18: Рейтинг темы: голосов - 18, средняя оценка - 4.83
Йуный плагиат-падаван)
176 / 119 / 45
Регистрация: 17.10.2022
Сообщений: 566

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

27.08.2023, 15:16. Показов 3766. Ответов 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
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6092 / 2785 / 1037
Регистрация: 01.06.2021
Сообщений: 10,176
28.08.2023, 23:14
Студворк — интернет-сервис помощи студентам
SmallEvil, я так понимаю тут какой-то обмен блоками длиной 2^k между массивами perm и new_perm, причем k вводится из клавиатуры.
0
 Аватар для Наталья8
518 / 368 / 65
Регистрация: 09.03.2016
Сообщений: 3,870
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
4831 / 1399 / 115
Регистрация: 21.04.2013
Сообщений: 8,535
29.08.2023, 03:54
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
проблема не решена
Какая проблема? Здесь нужно было накидать ассемблерные вставки или может тонко настроить компилятор на оптимизацию более жесткую? Внесите ясность.
0
Just Do It!
 Аватар для XLAT
4188 / 2643 / 654
Регистрация: 23.09.2014
Сообщений: 8,861
Записей в блоге: 3
29.08.2023, 04:21
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Внесите ясность.
там у него 3 вложенных фора,
что намекает на дубовый брутфорс,
а это уже подразумевает оптимизацию алгоритма,
точнее, его смену.

но так как сама задача не озвучена, то и взятки гладки...
0
 Аватар для Storm Screamer
4831 / 1399 / 115
Регистрация: 21.04.2013
Сообщений: 8,535
29.08.2023, 04:36
Цитата Сообщение от XLAT Посмотреть сообщение
что намекает на дубовый брутфорс,
Брут в один поток? Сурово.
0
Just Do It!
 Аватар для XLAT
4188 / 2643 / 654
Регистрация: 23.09.2014
Сообщений: 8,861
Записей в блоге: 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
Заблокирован
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
Заблокирован
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
Заблокирован
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
Заблокирован
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
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru