Сортировка неисправностей Google CodeJam 2018 Квалификаторы

Question

Я пытаюсь улучшить свои навыки программирования, решив пару вопросов Code Jam. Некоторое время я застревал на вопросе «Устранение неисправностей» из раундов квалификации в 2018 году. Мой код выдает ожидаемый результат с примером ввода в моей консоли, но онлайн-судья возвращает «Неправильный ответ».

Видимо, сортировка по неисправностям аналогична сортировке по пузырькам, за исключением того, что вместо сравнения i-го и i + 1-го элементов она сравнивает i-й и i + 2-й элементы, и если первый больше, чем последний, то элементы меняются местами. В вопросе говорится, что этот алгоритм имеет недостатки, так как массивы, такие как 897, после сортировки неисправностей вернут 798, что также не отсортировано. Задача состоит в том, чтобы проверить, способна ли сортировка проблем для заданного списка целых чисел успешно сортировать массив или нет, что является значением индекса первого элемента, который неуместен.

Мой код вводит количество тестов t и размер целочисленного списка. Затем я делаю копию и помещаю одну копию в сортировку по пузырькам, а другую - через сортировку по неисправностям. Затем я сравниваю их по элементам, и если найден индекс, в котором два элемента имеют разные целые числа, он выводится. Я не уверен, что я делаю здесь не так.

    #include<iostream>
    #include<vector>

    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;

    void swapVal(int& a, int& b)
    {
        int t = a;
        a = b;
        b = t;
    }

    int main()
    {
        int t;
        cin >> t;
        for (int i = 1; i <= t; i++)
        {
            int n;
            cin >> n;
            vector<int> bs(n);
            vector<int> ts(n);

            for (int i = 0; i < n; i++)
            {
                cin >> bs[i];
                ts[i] = bs[i];
            }

            //bubbleSort(bs, n);

            {
                bool bsSorted = false;
                while (!bsSorted)
                {
                    bsSorted = true;
                    for (int i = 0; i < n - 1; i++)
                    {
                        if (bs[i] > bs[i + 1])
                        {
                            swapVal(bs[i], bs[i + 1]);
                            bsSorted = false;
                        }
                    }
                }
            }

            //troubleSort(ts, n);
            {
                bool tsSorted = false;
                while (!tsSorted)
                {
                    tsSorted = true;
                    for (int i = 0; i < n - 2; i++)
                    {
                        if (ts[i] > ts[i + 2])
                        {
                            swapVal(ts[i], ts[i + 2]);
                            tsSorted = false;
                        }
                    }
                }
            }

            bool same = true;
            int minidx = 0;
            for (int i = 0; i < n; i++)
            {
                if (bs[i] != ts[i])
                {
                    same = false;
                    minidx = i;
                    break;
                }
            }

            if (same == true)
            {
                cout << "Case #" << i << ": OK" << endl;
            }
            else if (same == false)
            {
                cout << "Case #" << i << ": " << minidx;
            }
        }
    }

Я ожидаю, что судья даст мне галочку одобрения, но вместо этого он неоднократно возвращает «Неправильный ответ». Что я тут не так делаю?

Answer 1

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

cout << "Case #" << i << ": " << minidx<<'\n';

Может решить вашу проблему.

Несколько замечаний:

• if (same == true) эквивалентно if(same) и if (same == false) до if(!same).
• Уже есть std::swap.
• Некоторым людям может не понравиться вложенность в циклы с переменными с одинаковыми именами - вложенная переменная будет скрывать внешнюю.