Необходимо решить на с++ следующую задачу: можно ли отсортировать массив Аrr (по возрастанию), выполнив переворот ровно одного подотрезка (части массива) Аrr? Если да, вывести "yes" и индексы начала подотрезка. В противном случае вывести "no". Подробнее https://codeforces.com/problemset/problem/451/B.
Мною был создан следующий алгоритм: Во вложенном цикле создаётся частично перевернутый по индексам переворота i и j(которые и перебираются во вложенном цикле) массив. При совпадении полученного таким способом массива Q и заранее отсортированного массива В выводятся индексы i и j. Ниже приведена функция переворота части массива.
Далный алгоритм работает правильно, но на одном из тестов (70+к размер массива) тестировщик выводит превышение лимита времени. Как значительно оптимизировать перебор индексов или функцию переворота части массива для уменьшения времени работы программы? Функция переворота части массива:
vector<int> reverse(int l, int r, vector<int> A){
for(int i = l;i<=(l+r)/2;i++)
{
swap(A[i],A[l-i+r]);
}
return A;
}
Если существенная оптимизация невозможна прошу привести более быстрый способ решения задачи.