Оптимизация программы на Си

[evgenybal]

Условие:
Дана последовательность из N (1 ≤ N ≤ 100000) целых чисел и число K (|K| ≤ 100000). Сдвинуть всю последовательность (сдвиг - циклический) на |K| элементов вправо, если K – положительное и влево, если отрицательное.

Входные данные
В первой строке дано натуральное число N, во второй строке N целых чисел, а в последней целое число K. Все числа во входных данных не превышают 109.

Выходные данные
Требуется вывести полученную последовательность.

Примеры
входные данные
5
5 3 7 4 6
3
выходные данные
7 4 6 5 3

#include <stdio.h>

int main()
{
	int  k, i, j, n, tmp;
	scanf("%i", &n);
	int x[n];

	for (i = 0; i < n; i++)//вывод массива
	{
		scanf("%i", &x[i]);
	}

	scanf("%i", &k);
	if (k > 0)
	for (j = 0; j < k; j++)
		{
			for (i = n - 1; i > 0; i--)//принцип: перестановка последнего элемента на первое, путем простой перестановки. Кол-во перестановок зависит от числа k
			{
				tmp = x[i];
				x[i] = x[i - 1];
				x[i - 1] = tmp;

			}
		}
	else 
	for (j = 0; j < -k; j++)
		{
			for (i = 0; i < n-1; i++)
			{
				tmp = x[i];
				x[i] = x[i + 1];
				x[i + 1] = tmp;

			}
		}
	
	for (i = 0; i < n; i++) printf("%i ", x[i]);
	return 0;


}

Задачка взята с сайта, с поддержкой автоматической проверки кода путем серии тестов. Часть тестов программа не проходит, так как Превышено максимальное время работы. Вопрос: в чем может быть причина, так как я понимаю что мой код далек от идеала по краткости

[BDA]

Если реальный сдвиг производить не нужно, то после считывания всех данных можно вывести ответ:

i = k = (n - k % n) % n;
do {
    printf("%i ", x[i]);
    i = (i + 1) % n;
} while (i != k);

Проблема не в краткости кода, а в его временной сложности. Вы делаете K простых сдвигов, хотя можно или сразу вывести ответ, или произвести сразу сдвиг на К через дополнительный массив.

[max_prorok]

Возможно будет хуже и медленней, а может через связные списки будет быстрее работать?

[evgenybal]

Сообщение от BDA

Если реальный сдвиг производить не нужно, то после считывания всех данных можно вывести ответ:

i = k = (n - k % n) % n;
do {
    printf("%i ", x[i]);
    i = (i + 1) % n;
} while (i != k);

Проблема не в краткости кода, а в его временной сложности. Вы делаете K простых сдвигов, хотя можно или сразу вывести ответ, или произвести сразу сдвиг на К через дополнительный массив.

Честно? код шикарный. Сам бы наверное не додумался. Однако никак не могу осознать эту строчку: i = k = (n - k % n) % n;

[BDA]

Имеем желаемый сдвиг K. Если K больше N, то каждые N сдвигов массив будет возвращаться в исходное положение, так что сразу рассмотрим только сдвиг на K%N. Сдвиг в одну сторону на K аналогичен сдвигу в другую сторону на N-K. Поэтому рассматриваю сдвиг N+K%N. Этот сдвиг опять может быть больше N, так что (N+K%N)%N. Поскольку я только вывожу массив с определенного места, то мне нужно найти место, с которого выводить массив. Если сдвиг производится вправо, то место вывода левее начала массива и наоборот, поэтому формула (N-K%N)%N.

[max_prorok]

Сообщение от max_prorok

Возможно будет хуже и медленней, а может через связные списки будет быстрее работать?

Не слушайте меня. Вру я. Остапа понесло...

[max_prorok]

Но есть задумка, по поводу того, как использовать два массива. Если конечно условия позволяют.
Один массив содержит элементы, которые даются по заданию. Второй хранит в себе номера элементов первого массива. И когда ты сдвигаешь элементы вправо или влево, сам массив ты не трогаешь, а лишь поэлементно добавляешь число сдвигов во второй массив. Ну и конечно же, если сумма превышает число элементов первого массива, то просто откидывать количество элементов массива.
По идее должно работать быстрее, чем приведенный вами код, но не факт, что быстрее чем код приведенный BDA.