PKU 1089. Intervals. [판정:TLE]

Milkskin 2008. 12. 31. 23:08

나름 자료구조를 배웠다고 써먹어볼려고는 하는데

좀 쓸모가 있어야지 써먹든가 하지요 -_-

#include <iostream>
using namespace std;

class interval
{
public:
	int lb; // lower bound
	int ub; // upper bound
	interval *prev;
	interval *next;
	interval();
};

interval::interval()
{
	lb = 0;
	ub = 0;
	prev = NULL;
	next = NULL;
}

class ilist
{
public:
	interval *head;
	interval *tail;
	int count;
	ilist();
	int size();
	bool insertLast( int a, int b );
	interval* popFirst();
	void iswap( interval *ix, interval *iy );
	void selectionSort();
};

ilist::ilist()
{
	head = NULL;
	tail = NULL;
	count = 0;
}

int ilist::size()
{
	return count;
}

bool ilist::insertLast( int a, int b )
{
	int intersect = 0;
	interval *walker;

walker = this->head;

while( walker != NULL )
	{
		if( a <= walker->lb && walker->lb <= b )
		{
			intersect = 1;
			walker->lb = a;
		}
		if( a <= walker->ub && walker->ub <= b )
		{
			intersect = 1;
			walker->ub = b;
		}

walker = walker->next;
	}

if( intersect )
	{
		return false;
	}
	else
	{
		interval *fresh = new interval;

fresh->lb = a;
		fresh->ub = b;
		fresh->prev = this->tail;

if( size() == 0 )
		{
			this->head = fresh;
			this->tail = fresh;
		}
		else
		{
			fresh->prev->next = fresh;
			this->tail = fresh;
		}

count++;

return true;
	}
}

interval* ilist::popFirst()
{
	if( size() == 0 )
	{
		return NULL;
	}
	else
	{
		interval *temp = this->head;

this->head = temp->next;
		temp->next = NULL;
		if( this->head != NULL ) this->head->prev = NULL;
		if( size() == 1 ) this->tail = NULL;

count--;

return temp;
	}
}

void ilist::iswap( interval *ix, interval *iy )
{
	swap( ix->lb, iy->lb );
	swap( ix->ub, iy->ub );
}

void ilist::selectionSort()
{
	int i;
	int j;
	int n;
	interval *kthFront;
	interval *minpos;
	int min;
	interval *walker;

n = this->size();
	for( i = 0; i < n-1; i++ )
	{
		kthFront = this->head;

for( j = 0; j < i; j++ )
		{
			kthFront = kthFront->next;
		}

minpos = kthFront;
		min = minpos->lb;

walker = kthFront;
		while( walker != NULL )
		{
			if( min > walker->lb )
			{
				min = walker->lb;
				minpos = walker;
			}

walker = walker->next;
		}

if( minpos != kthFront )
		{
			iswap( minpos, kthFront );
		}
	}
}

int main()
{
	int n;
	int low;
	int up;
	ilist ins; // ins : INtervalS
	interval *temp;
	int i;

cin >> n;

while( n > 0 )
	{
		cin >> low >> up;

if( low <= up )
		{
			bool judge = ins.insertLast( low, up );

i = 0;
			while( !judge || i < ins.size() )
			{
				temp = ins.popFirst();

low = temp->lb;
				up = temp->ub;
				delete temp;

judge = ins.insertLast( low, up );
				i++;
			}
		}

n--;
	}

ins.selectionSort();

while( temp = ins.popFirst() )
	{
		cout << temp->lb << " " << temp->ub << endl;
		delete temp;
	}

return 0;
}

대충 계산해본 바로는

탐색에만 최대 O(4N²)을 소비하는 것 같으니 난감할 뿐 ㅋㅋㅋ

일단 TLE받은 것도 있고,

지금 바쁜것도 있고 하니 설명은 나중에 쓰거나 안쓰거나 할 예정입니다

조만간 배열로 다시 풀어서 제출할 예정이라는 -_-;

ps. Dlbo군은 또 정신놓고 이거 발행하는 짓은 하지 말기를 -_-a