Помогите найти runtime-error

Question

Если не сложно, скажите, пожалуйста, почему выдает runtime-error. Задача: Дан код, который получает последовательность целых положительных чисел, состоящих из единиц и нулей (без ведущих нулей) и сортирует её по убыванию количества единиц в числе. Числа, с одинаковым количеством единиц должны быть отсортированы по возрастанию значения. Формат ввода: В первой строке входных данных указано количество чисел в последовательности 1≤n≤1000. Во второй строке входных данных указано n чисел состоящих только из нулей и единиц 1≤ai≤1111111111.Числа разделены пробелами. Формат вывода: Отсортированная последовательность чисел, через пробелов. Программа благополучно проходит 4 теста на Яндекс-контест, а на тесте 5 выдает runtime-error.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int calc (std::string numbers)
{
int count = 0;
long int n = std::stoi (numbers);
while (n)
{
if (n%10 == 1)
count ++;
n/=10;
}
return count;
}

bool compare (std::string &left, std::string &right)
{
if (calc (left) == calc (right))
{
return std::stoi(left) <= std::stoi(right);
}

return calc(left) > calc(right);
}

int main(){
int count;
std::cin >> count;

std::vector<std::string> nums(count);
for(auto& line : nums) std::cin >> line;

std::sort(nums.begin(), nums.end(), compare);

for(auto& line : nums) std::cout << line << ' ';
}

Answer 1

К сожалению, соревнование закрытое, просто так не пускает. Ладно, раз уж завелся... Попробуйте такой код, хоть это и читерство...:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int ones(std::string&s)
{
    int o = 0;
    for(char c: s) if (c == '1') ++o;
    return o;
}

bool compare(std::string &left, std::string &right)
{
    int l = ones(left), r = ones(right);
    if (l != r) return l > r;

    l = left.size(), r = right.size();
    if (l != r) return l < r;

    for(int i = 0; i < l; ++i)
    {
        if (left[i] != right[i]) return left[i] < right[i];
    }
    return false;
}

int main()
{

    int count;
    cin >> count;

    std::vector<std::string> nums;
    for(int i = 0; i < count; ++i)
    {
        string m;
        cin >> m;
        nums.push_back(m);
    }

    std::sort(nums.begin(), nums.end(), compare);

    for(auto& line : nums) std::cout << line << ' ';
}

Answer 2

Строка return std::stoi(left) <= std::stoi(right); в компараторе возвращает истину для равных аргументов. Этого не должно быть, компаратор должен определять строгое неравенство. Эта ошибка приводит к падению программы во время сортировки.

Минимальный пример на моей машине – массив из семнадцати единиц. На вашей машине пример может быть другим, это зависит от компилятора:

$ uname -a
Linux debian 6.1.0-30-amd64 #1 SMP PREEMPT_DYNAMIC Debian 6.1.124-1 (2025-01-12) x86_64 GNU/Linux

$ g++ --version
g++ (Debian 12.2.0-14) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


$ g++ temp.cpp

$ echo 17 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | ./a.out
Segmentation fault

Простейшее исправление – замена нестрого неравенства на строгое.

P.S. Спасибо Harry за уточняющий вопрос.

БЛОГ НА HUSL

Помогите найти runtime-error

Ответы (2 шт):