Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помощ с оптимизацией кода

Артем Ка Ученик (184), открыт 1 неделю назад



Мое решение не проходит по времени, я думаю что он неэффективно перебирает m, подскажите как можно оптимизировать код. Братство это рядом стоящие элементы если что.
 #include   
using namespace std;
#define int int64_t
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector vec(n);
for (int i = 0; i < n; ++i) cin >> vec[i];
int ans = 0;
int m = -1;
for (int h = 0; h < n; ++h) {
if (vec[h] > m) m = vec[h];
}

for (int i = 0; i < n; ++i) {
for (int s = 2; s <= m; ++s) {
int l = vec[i] % s;
int anss = 1;
for (int h = i + 1; h < n; ++h) {
if (vec[h] % s == l) anss++;
else break;
}
if (anss > ans) ans = anss;
}
}
cout << ans << "\n";
}
return 0;
}
4 ответа
ChatGPT-4 Turbo Гуру (3760) 1 неделю назад
Оптимизируем. Быстро. Чётко. Эффективно. 100 рублей в год и начнем работать
Артем КаУченик (184) 1 неделю назад
рил турбо гпт
Папа Высший разум (123900) Артем Ка, на мыльном фото всё равно ничего разглядеть нереально, но если ты подсчитываешь кол-во чисел, имеющих одинаковый остаток от деления на что-то, то делаешь это самым идиотским способом, который только можно придумать. Изучай алгоритмы и дискретку, а то так и будешь уметь только перебирать решения в лоб, и ничего, кроме формошлёпства, тебе никогда в жизни не доверят.
Red Профи (994) 1 неделю назад
это означает что твоя программа работает не долго, а бесконечно, то есть неверно
Андрей Высший разум (430686) 1 неделю назад
Скриншоты текста задачи нечитаемы.

Вот так:
 #define int int64_t 
делать не надо. Никогда не надо.
Артем КаУченик (184) 1 неделю назад
Андрей Высший разум (430686) Полагаю, совсем не оптимальный вариант, и совершенно не уверен, что правильный, но что придумалось:
 a[1] mod m = ... = a[n] mod m = k
если:
НОД(a[1] - k, ..., a[n] - k) > max(1, k) 
Исходим из того, что НОД(x, 0) = x Для каждого нового k просто отнимаем 1 от всех a[i]. При этом значения a[i] < 0 разбивают массив на подмассивы и если длина подмассива не больше длины уже найденной максимальной последовательности, этот подмассив выбрасывается из рассмотрения. Писать громоздкий код на C++ не интересно, так что вариант решения на Python: https://onlinegdb.com/TpJJB8JGq
Татьяна КазаринаПрофи (731) 1 неделю назад
артем ка это я если что) там коменты закончились. Извините я е увидел что условия нечитаемы
ПапаВысший разум (123900) 1 неделю назад
Да, код прикольный. Перебор всех чисел до 10 в 18-й степени в качестве делителей, причём много раз, по числу элементов исходном в массиве.

А так-то, тут, наверное, можно оперировать разностями и факторизовать их. Факторизация нужна только до простых делителей, и не нужно хранить степени, достаточно самого факта присутствия. и тогда получится максимум штук 16 различных множителей, которые можно хранить в сортированном массиве. Но разность каждого числа с каждым - это 40 миллиардов разностей. Надо что-то поумнее придумать с перебором.
Похожие вопросы