Please Help, I am getting Time Limit each time i submit. I guess my program fell into infinite loop somewhere. Can anybody provide me some critical input.
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
#define TRUE 1
#define FALSE 0
typedef struct Node
{
int value;
struct Node *Next;
struct Node *Prev;
}Node;
typedef struct List
{
Node *Start;
Node *Head;
Node *Owner;
Node *Moved_To;
}List;
void Init_Data(List *list,int size);
void Init(List *list);
void Add_Node(List *list,int Data,int flag);
Node *Create_Node(void);
void Traverse_List(List *list);
void Move_Onto(List *list,int size,int num1,int num2);
void Move_Over(List *list,int size,int num1,int num2);
void Move_Block_Node(List *list,Node *node_a,Node *node_a_end,Node *node_b);
void Remove_Tops(List *list,Node *index,Node *Pos);
void Delete_List(List *list);
void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b);
void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b);
void Pile_Onto(List *list,int size,int num1,int num2);
void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);
void Pile_Over(List *list,int size,int num1,int num2);
void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);
int main(void)
{
int n;
int i = 0;
int cmd_a,cmd_b;
int number_1,number_2;
string ca,cb;
List *list = NULL;
cin >> n;
list = (List *)malloc(sizeof(List) * n);
Init_Data(list,n);
for(i = 0 ; i < n; ++i)
{
printf("%d: ",i);
Traverse_List(&list[i]);
printf("\n");
}
number_1 = number_2 = 0;
while(cin >> ca && ca != "quit")
{
cin >> number_1 >> cb >> number_2;
cmd_a = (ca == "move")? 1 : 2;
cmd_b = (cb == "onto")? 1 : 2;
if(number_1 == number_2)
cmd_a = 3;
switch(cmd_a)
{
case 1:
if(cmd_b == 1)
Move_Onto(list,n,number_1,number_2);
else
Move_Over(list,n,number_1,number_2);
break;
case 2:
if(cmd_b == 1)
Pile_Onto(list,n,number_1,number_2);
else
Pile_Over(list,n,number_1,number_2);
break;
default:
break;
}
for(i = 0 ; i < n; ++i)
{
printf("%d: ",i);
Traverse_List(&list[i]);
printf("\n");
}
}
for(i = 0 ; i < n; ++i)
Delete_List(&list[i]);
free(list);
return 0;
}
void Init(List *list)
{
list->Head = (Node *)malloc(sizeof(Node)*1);
list->Start = list->Head;
list->Head->Next = list->Head;
list->Head->Prev = list->Head;
list->Moved_To = list->Head;
list->Owner = NULL;
list->Head->value = 0;
}
void Init_Data(List *list,int size)
{
int i;
for(i = 0 ; i < size ; ++i)
{
Init(&list[i]);
Add_Node(&list[i] , i , TRUE);
}
}
void Move_Onto(List *list,int size,int num1,int num2)
{
int i = 0;
Node *node_a,*node_b;
if(list[num1].Moved_To == list[num2].Moved_To)
return;
node_a = list[num1].Owner;
node_b = list[num2].Owner;
Remove_Tops(list,list[num1].Moved_To,node_a);
Remove_Tops(list,list[num2].Moved_To,node_b);
MoveOnto(&list[num2],&list[num1],list[num1].Moved_To,node_a,node_b);
list[num1].Moved_To = list[num2].Moved_To;
}
void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b)
{
if(index->Next == node_a)
{
index->Prev = index;
index->Next = index;
}
node_a->Prev->Next = node_a->Next;
node_a->Next = node_b->Next;
node_a->Prev = node_b;
node_b->Next = node_a;
list->Moved_To->Prev = node_a;
}
void Move_Over(List *list,int size,int num1,int num2)
{
int i = 0;
Node *node_a,*node_b;
if(list[num1].Moved_To == list[num2].Moved_To)
return;
node_a = list[num1].Owner;
node_b = list[num2].Owner;
Remove_Tops(list,list[num1].Moved_To,node_a);
MoveOver(list[num1].Moved_To,list[num2].Moved_To,node_a,node_b);
list[num1].Moved_To = list[num2].Moved_To;
}
void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b)
{
if(a_index->Next == node_a)
{
a_index->Prev = a_index;
a_index->Next = a_index;
}
a_index->Prev = node_a->Prev;
node_a->Prev->Next = node_a->Next;
b_index->Prev->Next = node_a;
node_a->Next = b_index;
node_a->Prev = b_index->Prev;
b_index->Prev = node_a;
}
void Pile_Onto(List *list,int size,int num1,int num2)
{
int i = 0;
Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;
if(list[num1].Moved_To == list[num2].Moved_To)
return;
node_a_start = list[num1].Owner;
node_a_end = list[num1].Moved_To->Prev;
node_b = list[num2].Owner;
Remove_Tops(list,list[num2].Moved_To,node_b);
PileOnto(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);
node = node_a_start;
while(node != list[num2].Moved_To)
{
list[node->value].Moved_To = list[node_b->value].Head;
node = node->Next;
}
}
void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
if(index->Next == node_a_start)
{
index->Prev = index;
index->Next = index;
}
else
{
index->Prev = node_a_start->Prev;
}
node_a_start->Prev->Next = node_a_end->Next;
node_a_end->Next = node_b->Next;
node_a_start->Prev = node_b;
node_b->Next = node_a_start;
list->Head->Prev = node_a_end;
}
void Pile_Over(List *list,int size,int num1,int num2)
{
int i = 0;
Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;
if(list[num1].Moved_To == list[num2].Moved_To)
return;
node_a_start = list[num1].Owner;
node_a_end = list[num1].Moved_To->Prev;
node_b = list[num2].Moved_To->Prev;
node = node_a_start;
PileOver(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);
while(node != list[num2].Moved_To)
{
list[node->value].Moved_To = list[num2].Head;
node = node->Next;
}
}
void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
if(index->Next == node_a_start)
{
index->Prev = index;
index->Next = index;
}
else
{
index->Prev = node_a_start->Prev;
}
node_a_start->Prev->Next = node_a_end->Next;
node_a_end->Next = node_b->Next;
node_a_start->Prev = node_b;
node_b->Next = node_a_start;
list->Head->Prev = node_a_end;
}
void Remove_Tops(List *list,Node *index,Node *Pos)
{
Node *Curr = Pos->Next;
Node *Tmp;
while(Curr != index)
{
Tmp = Curr->Next;
list[Curr->value].Owner->Prev = list[Curr->value].Head;
list[Curr->value].Owner->Next = list[Curr->value].Head;
list[Curr->value].Head->Next = list[Curr->value].Owner;
list[Curr->value].Head->Prev = list[Curr->value].Owner;
list[Curr->value].Moved_To = list[Curr->value].Head;
Curr = Tmp;
}
Pos->Next = index;
list[Pos->value].Moved_To->Prev = Pos;
}
void Delete_List(List *list)
{
Node *Curr;
free(list->Owner);
free(list->Head);
list->Head = NULL;
}
Node *Create_Node(void)
{
Node *node = (Node *)malloc(sizeof(Node)*1);
node->Next = NULL;
node->Prev = NULL;
return node;
}
void Add_Node(List *list,int Data,int flag)
{
Node *node = Create_Node();
Node *Head = list->Head;
node->value = Data;
node->Prev = Head->Prev;
node->Next = Head;
Head->Prev->Next = node;
Head->Prev = node;
if(flag)
list->Owner = node;
}
void Traverse_List(List *list)
{
Node *Curr;
if(list->Head->Prev == list->Head || list->Head->Next == list->Head)
{
return;
}
Curr = list->Head->Next;
while(Curr != list->Head)
{
printf("%d",Curr->value);
Curr = Curr->Next;
if(Curr != list->Head)
printf(" ");
}
}
