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

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

27.08.2023, 15:16. Показов 4090. Ответов 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
6312 / 3035 / 1053
Регистрация: 01.06.2021
Сообщений: 11,544
28.08.2023, 23:14
Студворк — интернет-сервис помощи студентам
SmallEvil, я так понимаю тут какой-то обмен блоками длиной 2^k между массивами perm и new_perm, причем k вводится из клавиатуры.
0
Нарушитель
623 / 381 / 67
Регистрация: 09.03.2016
Сообщений: 4,218
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
4962 / 1541 / 119
Регистрация: 21.04.2013
Сообщений: 9,040
29.08.2023, 03:54
Цитата Сообщение от DOPIXKMNLD Посмотреть сообщение
проблема не решена
Какая проблема? Здесь нужно было накидать ассемблерные вставки или может тонко настроить компилятор на оптимизацию более жесткую? Внесите ясность.
0
Just Do It!
 Аватар для XLAT
4219 / 2680 / 656
Регистрация: 23.09.2014
Сообщений: 9,235
Записей в блоге: 3
29.08.2023, 04:21
Цитата Сообщение от Storm Screamer Посмотреть сообщение
Внесите ясность.
там у него 3 вложенных фора,
что намекает на дубовый брутфорс,
а это уже подразумевает оптимизацию алгоритма,
точнее, его смену.

но так как сама задача не озвучена, то и взятки гладки...
0
 Аватар для Storm Screamer
4962 / 1541 / 119
Регистрация: 21.04.2013
Сообщений: 9,040
29.08.2023, 04:36
Цитата Сообщение от XLAT Посмотреть сообщение
что намекает на дубовый брутфорс,
Брут в один поток? Сурово.
0
Just Do It!
 Аватар для XLAT
4219 / 2680 / 656
Регистрация: 23.09.2014
Сообщений: 9,235
Записей в блоге: 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
Ответ Создать тему
Новые блоги и статьи
сукцессия 25. Хронология ошибок
anaschu 12.07.2026
# От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .
сукцессия 24. Промежуточное общее описание модели
anaschu 12.07.2026
Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .
сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры.
anaschu 12.07.2026
Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато
anaschu 11.07.2026
Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .
Сукцессия 20. Война автоботов. Делаем ставки. Лёд против "пш-пш!".
anaschu 11.07.2026
Битва ИИ в ризосфере: Как мы скрестили жесткие ОДУ, закон Фика и «подземный шантаж» Уважаемые коллеги! Хочу поделиться уникальным опытом ведения междисциплинарной компьютерной разработки. Прямо. . .
Сукцессия 19. Какие выводы я сделал из модели? Часть 2.Внутримикоризный стехиометрический буфер и хроно-дискретные зоны экспансии
anaschu 11.07.2026
Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования
Сукцессия 18. Какие выводы я сделал из войны грибов с деревьями? Часть 1- рассказ и немного про термины
anaschu 11.07.2026
Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования Система ОДУ описывает динамику изменения массы различных компонентов системы во времени. Ключевой. . .
Просветление в 5 секунд
kumehtar 10.07.2026
Андрей Веретенников выдал фразу недавно: "Вам не обязательно кем-то себя считать"
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru