Ошибки времени выполнения при использовании векторов большого размера в C++

    #include <iostream>
    #include <vector>

    // ТЕСТ ТЕСТ ТЕСТ ТЕСТ
    #include <cstdlib>
    #include <ctime>

    using namespace std;

    struct Team
    {
    int solP; // Количество решенных задач
    int numP; // Количество штрафов
    int rank;
    };

    int main()
    {
    srand(time(0)); // ТЕСТ ТЕСТ ТЕСТ ТЕСТ 
    vector<Team> teams; // 0 обозначает команду 1
    vector<int> favoriteTeam; // Заполнен рангами любимой команды
    vector<int> rank; // Заполнен рангами с последнего события
    int numTeams;
    int numEvents;

    //cin >> numTeams >> numEvents; // Считывание строки 1 // ТЕСТ ТЕСТ ТЕСТ
    numTeams = (rand() % (int)10e5) + 1;
    numEvents = (rand() % (int)10e5) + 1;
    // ТЕСТ ТЕСТ ТЕСТ
    teams.resize(numTeams);
    favoriteTeam.resize(numEvents);
    rank.resize(numTeams);
    for (int i = 0; i < numTeams; i++)
    {
        Team temp;
        temp.solP = 0;
        temp.numP = 0;
        temp.rank = 1;
        teams[i] = temp;
    }

    for (int i = 0; i < numEvents; i++)
    {
        int t, p;
        //cin >> t >> p; ТЕСТ ТЕСТ ТЕСТ
        t = (rand() % numTeams) + 1;
        p = (rand() % 1000) + 1;
        // ТЕСТ ТЕСТ ТЕСТ
        ++teams[t - 1].solP;
        teams[t - 1].numP += p;

        // ВЫЗОВ ДЛЯ УПОРЯДОЧИВАНИЯ
        int modifier;
        int bestIndex;
        vector<bool> tie(numTeams);
        vector<bool> used(numTeams, false);

        // Настройка вектора рангов
        for (int i = 0; i < numTeams; i++)
        {
            bestIndex = i;
            for (int j = 0; j < numTeams; j++)
            {
                if (i == j || used[j]) continue;
                if (used[i] || teams[j].solP > teams[bestIndex].solP || teams[j].solP == teams[bestIndex].solP && teams[j].numP <= teams[bestIndex].numP)
                {
                    bestIndex = j;
                }
            }
            rank[i] = bestIndex;
            used[bestIndex] = true;
        }

        // Настройка вектора ничьих
        for (int i = 0; i < numTeams; i++)
        {
            if (i != 0 && teams[rank[i]].solP == teams[rank[i - 1]].solP && teams[rank[i]].numP == teams[rank[i - 1]].numP)
            {
                tie[i] = true;
            }
            else tie[i] = false;
        }

        // Установка ранга для каждой команды
        modifier = 0;
        for (int i = 0; i < numTeams; i++)
        {
            if (tie[i]) modifier++;
            teams[rank[i]].rank = i + 1 - modifier;
        }

        // Установка вывода
        favoriteTeam[i] = teams[0].rank;
    }

    //cout << endl;
    for (int i = 0; i < numEvents; i++)
    {
        cout << favoriteTeam[i] << endl;

    }

    cout << clock() / (double)CLOCKS_PER_SEC << endl;

    return 0;
    }

Ответ

Проблема, с которой вы столкнулись, может быть связана с чрезмерным использованием памяти и неэффективными алгоритмами, которые могут привести к превышению времени выполнения или утечкам памяти при работе с большими объёмами данных. Давайте рассмотрим несколько аспектов вашего кода и предложим возможные решения.

Проблемы в коде

1. Инициализация векторов и их размер:
   Вы используете vector<Team> teams и два других вектора, что может занять значительное количество памяти. Когда вы создаете numTeams или numEvents, которые могут достигать 1 миллиона, вы находитесь на грани аренды памяти, и ваш компьютер может просто не иметь достаточно оперативной памяти для выполнения кода.

2. Алгоритм сортировки:
   Ваш текущий алгоритм для определения рангов команд — это алгоритм с временной сложностью O(n^2), который будет работать неэффективно с большими размерами векторов. Это также может привести к замедлению выполнения программы.

3. Логику использования переменной used:
   Ваша переменная used может вызвать дополнительные проверки, что делает ваш алгоритм ещё более неэффективным.

Рекомендуемые изменения

1. Изменить алгоритм сортировки:
   Вместо использования вложенного цикла для определения рангов, вы можете создать отдельный вектор, который будет хранить пары (объект команды и её индекс), после чего отсортировать его по убыванию решенных задач и по возрастанию штрафов.

   #include <algorithm>
   
   // Используйте стандартный метод сортировки
   vector<pair<Team, int>> indexedTeams;
   for (int i = 0; i < numTeams; ++i) {
      indexedTeams.emplace_back(teams[i], i);
   }
   
   sort(indexedTeams.begin(), indexedTeams.end(), [](const auto& a, const auto& b) {
      if (a.first.solP != b.first.solP)
          return a.first.solP > b.first.solP;
      return a.first.numP < b.first.numP;
   });

2. Оптимизация памяти:
   Попробуйте выделить память более экономно. Например, если вам не нужна слишком большая память, попробуйте использовать std::vector.reserve(), чтобы избежать множества переполнений при добавлении элементов.

3. Использовать unordered_map для хранения штрафов:
   Рассмотрите возможность использования std::unordered_map для хранения и обработки команд, если это приемлемо для вашей задачи.

Пример исправленного кода

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

struct Team {
    int solP; // количество решенных задач
    int numP; // штраф
    int rank;
};

int main() {
    srand(time(0));

    int numTeams = (rand() % (int)10e5) + 1;
    int numEvents = (rand() % (int)10e5) + 1;

    vector<Team> teams(numTeams, {0, 0, 0});
    vector<int> favoriteTeam(numEvents);

    for (int i = 0; i < numEvents; ++i) {
        int t = rand() % numTeams;
        int p = (rand() % 1000) + 1;
        ++teams[t].solP;
        teams[t].numP += p;

        vector<pair<Team, int>> indexedTeams;
        for (int j = 0; j < numTeams; ++j) {
            indexedTeams.emplace_back(teams[j], j);
        }

        sort(indexedTeams.begin(), indexedTeams.end(), [](const auto& a, const auto& b) {
            if (a.first.solP != b.first.solP)
                return a.first.solP > b.first.solP;
            return a.first.numP < b.first.numP;
        });

        for (int j = 0; j < numTeams; ++j) {
            teams[indexedTeams[j].second].rank = j + 1;
        }

        favoriteTeam[i] = teams[0].rank;
    }

    for (int i = 0; i < numEvents; ++i) {
        cout << favoriteTeam[i] << endl;
    }

    return 0;
}

Заключение

Теперь ваш алгоритм должен работать более эффективно и устойчиво, даже при больших вводах данных. Убедитесь, что вы тестируете код с различными размерами входных данных, чтобы гарантировать, что он обрабатывается в течение разумного времени и с достаточной памятью.