fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. int count;
  5.  
  6. struct node{
  7. 	int value;
  8. 	struct node* next;
  9. };
  10.  
  11. int constructFinal(int *final,struct node **parent,struct node **output,int value){
  12. 	if(final[value - 1] == 1)
  13. 		return 0;
  14. 	final[value - 1] = 1;
  15. 	count++;
  16. 	struct node* temp;
  17. 	temp = parent[value-1];
  18. 	while(temp!= NULL){
  19. 		constructFinal(final,parent,output,temp->value);
  20. 		temp = temp->next;
  21. 	}
  22. }
  23.  
  24. int findIndex(int currentElement,struct node** output,int lower,int upper){
  25. 	if(lower >= upper)
  26. 		return lower;
  27. 	int mid =lower + ( upper - lower )/2;
  28. 	if(output[mid]->value < currentElement)
  29. 		return findIndex(currentElement,output,mid+1,upper);
  30. 	else if(output[mid]->value > currentElement)
  31. 		return findIndex(currentElement,output,lower,mid);
  32. }	
  33.  
  34. int main(){
  35. 	int numOfInp,sizeOfInp,i,currentElement,sizeOfOut,indexBinary,indexAdded;
  36. 	struct node *temp,*tempIter;
  37. 	numOfInp=1;
  38. 	while(numOfInp--){
  39. 		scanf("%d",&sizeOfInp);
  40. 		struct node **output; // if I initialise normal initialisation, I may not get the data as 0 by default, hence callocing
  41. 		struct node **parent;
  42. 		int *input;
  43. 		input = (int *)calloc(sizeOfInp,sizeof(int));
  44. 		for(i=0 ; i< sizeOfInp ; i++)
  45. 			scanf("%d",&input[i]);
  46.  
  47. 		parent = (struct node**)calloc(sizeOfInp, sizeof(struct node*));
  48.  
  49. 		output = (struct node**)calloc(sizeOfInp, sizeof(struct node*));
  50. 		sizeOfOut = 0;
  51. 		for(i=0;i<sizeOfInp;i++){
  52. 			indexBinary = -1;
  53. 			currentElement = input[i];
  54. 			if(sizeOfOut == 0){
  55. 				output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
  56. 				output[sizeOfOut]->value = currentElement;
  57. 				indexAdded = sizeOfOut;
  58. 				sizeOfOut++;
  59. 			}
  60. 			else{
  61. 				if(currentElement > output[sizeOfOut-1]->value){
  62. 					output[sizeOfOut] = (struct node*)calloc(1,sizeof(struct node));
  63. 					output[sizeOfOut]->value = currentElement;
  64. 					indexAdded = sizeOfOut;
  65. 					sizeOfOut++;
  66. 				}
  67. 				else{
  68. 					indexBinary = findIndex(currentElement,output,0,sizeOfOut-1);
  69. 					temp = (struct node*)calloc(1,sizeof(struct node));
  70. 					temp->next = output[indexBinary];
  71. 					output[indexBinary] = temp;
  72. 					output[indexBinary]->value = currentElement;
  73. 					indexAdded = indexBinary;
  74. 				}
  75. 			}
  76.  
  77. 			//parent[currentElement-1] = (struct node*)calloc(sizeof(struct node));
  78. 			if(indexAdded > 0){
  79. 				tempIter = output[indexAdded-1];
  80. 				while(tempIter != 0 && tempIter->value < currentElement){				//for all the elements in the previous bucket
  81. 					temp = (struct node*)calloc(1,sizeof(struct node));	//add the values to parent
  82. 					temp->next = parent[currentElement-1];
  83. 					parent[currentElement-1] = temp;
  84. 					parent[currentElement-1]->value = tempIter ->value;
  85. 					tempIter = tempIter->next;
  86. 				}
  87. 			}
  88. 			else{
  89. 				parent[currentElement-1] = NULL;	// these are the elements in the first bucket of output
  90. 			}
  91. 		}
  92.  
  93. 		int *final;
  94. 		final = (int*)calloc(sizeOfInp,sizeof(int));
  95. 		temp = output[sizeOfOut -1];
  96. 		count=0;
  97. 		while(temp != NULL){
  98. 			constructFinal(final,parent,output,temp->value);
  99. 			temp=temp->next;
  100. 		}
  101. 		printf("%d\n",count);
  102. 		for(i=0;i<sizeOfInp;i++)
  103. 			if(final[i]==1)
  104. 				printf("%d ",i+1);
  105. 		printf("\n");
  106. 		free(output);
  107. 		free(parent);
  108.  
  109. 	}
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
5
2 1 4 5 3
stdout
copy 
4
1 2 4 5
https://ideone.com/RO5Wko
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!