INSERTION

https://algospot.com/judge/problem/read/INSERTION

algospot.com :: INSERTION

삽입정렬의 초기값을 구하는 문제임.

1번의 Step마다 내부 Index를 참조하고 삭제해야함.

STL의 vector나 list를 사용하면 시간초과가됨.

재정의하여 내부 참조는 꼼수를 사용하여 해결함.

#include 
#include 

typedef struct node{
	node * prev;
	node * next;
	int value;
}NODE;
int I[50001];
int A[50001];
NODE * Start;
NODE * End;
int Size;
int hN;
int move(int index)
{
	NODE * TARGET;
	int VALUE;
	if (index < hN)
	{
		TARGET = End;
		for (int i = 0; i < index; i++, TARGET = TARGET->prev);
	}
	else
	{
		TARGET = Start;
		for (int i = 0; i < Size - index - 1; i++, TARGET = TARGET->next);
	}

	VALUE = TARGET->value;
	if (TARGET->prev != NULL)TARGET->prev->next = TARGET->next;
	if (TARGET->next != NULL)TARGET->next->prev = TARGET->prev;
	
	if (TARGET == Start) Start = TARGET->next;
	else if (TARGET == End) End = TARGET->prev;

	free(TARGET);
	--Size;
	return VALUE;
}
int main()
{
	int C;
	for (scanf("%d", &C); C>0; C--)
	{
		int N;
		scanf("%d", &N);
		NODE *CUR = NULL;
		for (int i = 0; ivalue = i + 1;
			TEMP->prev = NULL; TEMP->next = NULL;
			TEMP->prev = CUR;
			if (CUR != NULL)
				CUR->next = TEMP;
			else
				Start = TEMP;

			CUR = TEMP;

			scanf("%d", &I[i]);
		}
		Size = N;
		hN = N / 2;
		End = CUR;
		/// PROCESS
		for (int i = N - 1; i>-1; i--)
			A[i] = move(I[i]);
		
		for (int i = 0; i < N; i++)
			printf("%d%c", A[i], (i != N - 1) ? ' ' : '\n');
	}
	return 0;
}