글 읽기 - 반례를 못찾겟습니다

john6014 9달 전 0

음 계속 시간초과가 뜨는데... 특정 값에서 무한루프가 도는것 같습니다만.. 도저히 못찾겟습니다. 어디가 틀린건가요??

											#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

void Before(int * Pre, int * In, int * Post, int start, int end);
void After(int * Pre, int * In, int * Post, int start, int end);

int main()
{
	int * Post, *In, *Pre;
	int i, N, pivot;

	scanf("%d", &N);

	Post = (int*)malloc(sizeof(int) * N);
	In = (int*)malloc(sizeof(int) * N);
	Pre = (int*)malloc(sizeof(int) * N);

	for (i = 0; i < N; i++)
		scanf("%d", &In[i]);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &Post[i]);
		Pre[i] = 0;
	}

	pivot = Post[N - 1];

	for (i = 0; i < N; i++)
		if (In[i] == pivot)
		{
			Pre[0] = In[i];
			In[i] = -1;
			break;
		}

	Before(Pre, In, Post, 0, i - 1);
	After(Pre, In, Post, i, N - 1);

	for (i = 0; i < N; i++)
		printf("%d ", Pre[i]);

	free(Pre);	free(In);
	free(Post);	return 0;
}

void Before(int * Pre, int * In, int * Post, int start, int end)
{
	int i, j, Ltemp, Rtemp, Lsize , Rsize , save;

	for (i = end; i >= start; i--)
	{
		Lsize = 0;	Rsize = 0;
		for (j = end; j >= start; j--)
			if (Post[i] == In[j])
				break;

		save = j;

		if (j != start)
		{
			if (j - 1 == start)
				Lsize++;
			else
			{
				Ltemp = j - 1;

				while (1)
				{
					if (Ltemp == start - 1)
						break;

					if (In[Ltemp] == -1)
						break;

					Ltemp--;	Lsize++;
				}
			}
		}

		if (j != end)
		{
			if (j + 1 == end)
				Rsize++;
			else
			{
				Rtemp = j + 1;

				while (1)
				{
					if (Rtemp == end + 1)
						break;

					if (In[Rtemp] == -1)
						break;

					Rtemp++;	Rsize++;
				}
			}
		}

		for (j = end + 1; j >= start; j--)
			if (Pre[j] == 0)
				break;

		Pre[j - Lsize - Rsize] = In[save];
		In[save] = -1;
	}
}

void After(int * Pre, int * In, int * Post, int start, int end)
{
	int i, j, Ltemp, Rtemp, Lsize , Rsize , save;

	for (i = end - 1; i >= start; i--)
	{
		Lsize = 0;	Rsize = 0;
		for (j = end; j > start; j--)
			if (Post[i] == In[j])
				break;

		save = j;

		if (j != start + 1)
		{
			if (j - 1 == start + 1)
				Lsize++;
			else
			{
				Ltemp = j - 1;

				while (1)
				{
					if (Ltemp == start)
						break;

					if (In[Ltemp] == -1)
						break;

					Ltemp--;	Lsize++;
				}
			}
		}

		if (j != end)
		{
			if (j + 1 == end)
				Rsize++;
			else
			{
				Rtemp = j + 1;

				while (1)
				{
					if (Rtemp == end + 1)
						break;

					if (In[Rtemp] == -1)
						break;

					Rtemp++;	Rsize++;
				}
			}
		}

		for (j = end; j > start; j--)
			if (Pre[j] == 0)
				break;

		Pre[j - Lsize - Rsize] = In[save];
		In[save] = -1;
	}
}
										

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

반례를 못찾겟습니다

john6014 9달 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱