0 / 0 / 0
Регистрация: 12.04.2022
Сообщений: 3
1

TLE и как можно оптимизировать код

12.04.2022, 20:43. Показов 427. Ответов 6
Метки нет (Все метки)

Доброго времени суток! Написанный код работает, как нужно, но при некоторых ситуациях выдaет TLE. Предполагаю, что это из-за вложенного цикла. Какие советы вы могли бы дать, чтобы оптимизировать код?

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main() {
 
    string s;
    getline(cin,s);
    vector <string> v;
    map <int, string> mp;
 
    auto x = s.begin();
    auto it = find(s.begin(), s.end(), ' ') ;
    while (it != s.end()) {
        v.push_back(s.substr(x-s.begin(), it-x));
        x = it+1;
        it = find(x, s.end(), ' ');
    }
    v.push_back(s.substr(x-s.begin(), it-x));
    int n = v.size();
 
    for (int i = 1; i <= n; i++) {
        mp[i] = v[i-1];
    }
 
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
 
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " : ";
        for (int j = 1; j <= n; j++)
            if (mp[j] == v[i])
                cout << j << ' ';
        cout << '\n';
    }
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.04.2022, 20:43
Ответы с готовыми решениями:

Как можно оптимизировать код? Код считывает кол-во скобок
s = input() s = cheked = set() ans = 0 L = len(s) for l in range(L+1 if L % 2 else L, 1, -2):...

Как можно оптимизировать код?
Здравствуйте. Написал скрипт, позволяющий считывать с сервера картинку, преобразовывать ее в...

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

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

Как можно оптимизировать код
using System; using System.Collections.Generic; using System.Linq; using System.Text; using...

6
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
12.04.2022, 22:49 2
Цитата Сообщение от anaconda_ Посмотреть сообщение
Какие советы вы могли бы дать, чтобы оптимизировать код?
Совет: вместе с кодом прикладывай и описание самой задачи
0
2477 / 1904 / 951
Регистрация: 21.12.2010
Сообщений: 3,473
Записей в блоге: 10
13.04.2022, 07:55 3
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <utility>
using namespace std;
 
int main() 
{
    string s;
    getline(cin, s);
    auto cmp = [](auto const& a, auto const& b) {return a.second < b.second; };
    set<pair<vector<int>, string>, decltype(cmp)> st{cmp};
 
    auto x = s.begin();
    auto it = find(s.begin(), s.end(), ' ');
    int i = 0;
    for (; it != s.end(); ++i) {
        auto [iter, bl] = st.emplace(vector{ i + 1 }, s.substr(x - s.begin(), it - x));
        if (!bl)
        {
            const_cast<vector<int>&>(iter->first).push_back(i + 1);
        }
        x = it + 1;
        it = find(x, s.end(), ' ');
    }
    auto [iter, bl] = st.emplace(vector{ i + 1 }, s.substr(x - s.begin(), it - x));
    if (!bl)
    {
        const_cast<vector<int>&>(iter->first).push_back(i + 1);
    }
 
    for (auto& [v, s] : st)
    {
        cout << s << " : ";
        for (auto n : v)
        {
            cout << n << " ";
        }
        cout << "\n";
    }
}
 
// dfdf ttt ww tt ttt
1
Продавец времени
7107 / 3989 / 917
Регистрация: 12.03.2015
Сообщений: 18,769
13.04.2022, 08:17 4
Цитата Сообщение от anaconda_ Посмотреть сообщение
но при некоторых ситуациях выдaет TLE
Чо такое "TLE"?
0
0 / 0 / 0
Регистрация: 12.04.2022
Сообщений: 3
13.04.2022, 10:33  [ТС] 5
Задан текст, состоящий из слов, разделенных пробелами. Каждое слово может встречаться в тексте несколько раз. В этом случае у него есть несколько вхождений. Программа должна вывести все различные слова в алфавитном порядке. Кроме того, для каждого слова требуется вывести номера всех его вхождений в порядке возрастания. Спасибо за совет!

Добавлено через 14 минут
nonedark2008, спасибо за совет!

Добавлено через 1 минуту
Verevkin, time-limit exceeded, ошибка времени выполнения

Добавлено через 1 минуту
igorrr37, спасибо!
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
13.04.2022, 23:59 6
Цитата Сообщение от anaconda_ Посмотреть сообщение
Предполагаю, что это из-за вложенного цикла. Какие советы вы могли бы дать, чтобы оптимизировать код?
Верно, из-за вложенного цикла у твоей конструкции получается квадратичная сложность, что много для такой задачи. Оптимальное по производительности решение уже показал igorrr37, но его можно легко упростить и убрать страшные const_cast.
По сути все сводится к заполнению контейнера std::map<std::string, std::vector<int>>, где ключ - слово, а значение - массив с позициями. Элементы в std::map упорядочены, так что после заполнения достаточно его просто вывести.
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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
 
using namespace std;
int main() {
    map<string, vector<int>> mp;
    string s;
 
    getline(cin, s);
 
    string curWord;
    int wordNum = 0;
    istringstream ss(s);
    while (getline(ss, curWord, ' '))
    {
        ++wordNum;
        mp[curWord].push_back(wordNum);
    }
 
    for (auto& [word, wordNums] : mp)
    {
        cout << word << " :";
        for (int pos : wordNums)
            cout << " " << pos;
        cout << endl;
    }
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 12.04.2022
Сообщений: 3
14.04.2022, 06:38  [ТС] 7
nonedark2008, спасибо за вашу помощь!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.04.2022, 06:38
Помогаю со студенческими работами здесь

Как можно оптимизировать код?
#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; int main() {...

Как можно оптимизировать код?
import random import string try: # Создание пустых списков total = result = ...

Как можно оптимизировать код?
Здравствуйте! Столкнулся с проблемой. VBA стал ругаться на сильно длинный код. Надо его...

Как можно оптимизировать код?
Как можно оптимизировать код? Интересует только js let init = () =&gt; { block1 =...

Как можно оптимизировать код?
#include &lt;stdio.h&gt; unsigned int A; int main(){ int i,p; p=6; for(i=5;i&gt;=0;i--){ __asm{...

Как можно оптимизировать код?
Всем привет, вопрос такой, как оптимизировать данный код? private void...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru