[I know my code is not neat , but you needn't go logically through all , i promise]
I wanted to print out number at position 'k' of vector numb when user enters -1 and this is what i tried doing in Line 15. But i am surprised- why doesnt my program print anything when user enters -1 ? Please help , thanks in advanced :)
Here's Code :-
Thanks so much for re-remainding me my old mistake ne555 :)
But now i am running into deeper troubles - its my algorithmic mistake i think.
In my code i input some numbers and store them in 'numb' applying Binary Search Technique to insert numbers into numb keeping numb always sorted . If entered nos. is -1 , then i print kth smallest nos & k is given to us beforehand. In line 15,20,22,25 & also in line 33/34 i cout '|' merely for testing purpose .
Ex. Input :
6 //n
2 //k
3
2
-1
-1
1
-1
Its output should be 3 \n3 \n 2 but my code prints three 3s and doesnt even inserts all nos. not -1 into numbs . Thats major bug (Line 16 to 28) - code doesnt inserts all numbers properly into numb .
Could you generously enough tell remedy or a different algorithm which would be simple yet effecient ?
The insertion operation is the expensive part of your algorithm.
You gain nothing by using binary search, so just do `insertion sort' O(n^2)
If the constraints make that too much, consider using a binary tree. That way you will have O(n lg n) for the construction, however retrieve the 'k' element would be linear.
Yeah You really have a point . So i switch my code and used priority queue to push them in ascending order but now have problem in printing k. Is there any function that would print kth nos. in priority queue ? What i am doing was to pop out k elements to another variable and then print topmost element left , then again push back elements removed , but this proves costly to time and leaves my code into time limit . Here's that code if you wish to look at :-
#include<iostream>
#include<algorithm>
#include<queue>
usingnamespace std;
int main() {
int i,j,n,k,elec=0,tmp;
priority_queue< int, vector<int>, greater<int> > numbo;
queue<int> dustbin;
cin>>n>>k;
while (n--) {
cin>>tmp;
if (tmp!=-1) {
numbo.push(tmp);
} else {
for (i=0;i<k-1;i++) {
dustbin.push(numbo.top());
numbo.pop();
}
cout<<numbo.top()<<endl;
for (i=0;i<k-1;i++) {
numbo.push(dustbin.front());
dustbin.pop();
}
}
}
}
And also i didn't try to implement binary tree because i simply couldn't understand it - so its link showing basic/elementry binary tree would be much apprecieated :)
Sorry i forgot to mention it :-
n <= 100000 k <= 1000 And every element <= 100000
where n is number of queries , k is the nos. that we need to print out ,ie we need to printout kth minimumost nos. entered till now except -1 .
@coder777 : Obviously to win a medal at prestigious IOI,ACM :D
@ne555 : Yes we definatly needn't need to sort 'n' numbers , neither there is any need to store them , we could first take first n numbers then sort it and then ignore numbers greater than kth smallest number . But i dont think that it would be any countable gain on effeciency . But still let me try and see if you say .