Unexpected Output in program ?!?!

[Maggi Iggam]

[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 :-

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    int i,n,k,tmp,nc=0,kc,left,right,middle;
    vector<int> numb;
    short int j=0;
    cin>>n>>k;
    for (i=0;i<k;i++) {cin>>tmp;numb.push_back(tmp);}
    partial_sort(numb.begin(),numb.end(),numb.end());
    kc=numb[k-1];
    for (;i<n;i++) {
        cin>>tmp;
        if (tmp==-1) {cout<<"|"<<numb.at(k)<<endl;} else {
            left=0;right=i;
            while (left<=right) {
                  j=0;
                  middle=(left+right)/2;
                  if (numb[middle]==tmp) {numb.insert(numb.begin()+middle,tmp);cout<<"|"<<numb.at(middle)<<endl;break;}
                  if (numb[middle]>tmp) {
                     if (j==-1) {numb.insert(numb.begin()+middle-1,tmp);cout<<"|"<<numb.at(middle-1)<<endl;break;} else {j=1;}
                     right=middle-1;
                  } else {
                     if (j==1) {numb.insert(numb.begin()+middle+1,tmp);cout<<"|"<<numb.at(middle+1)<<endl;break;} else {j=-1;}
                     left=middle+1;
                  }
            }
        }
    }
    cout<<"|"<<endl;
    vector<int>::reverse_iterator rit;
    for ( rit=numb.rbegin() ; rit < numb.rend(); ++rit )
    cout << " " << *rit;
}

[Peter87]

Shouldn't you give i a value on line 13?

[Maggi Iggam]

Well @Peter87 , 'i' is already initialized at Line 10.

[Peter87]

Yes, but after that line i == n so the second loop will never run.

[Maggi Iggam]

Oh , yeah -thats good point , i should have replaced n with k !
Thanks @Peter87 !

Okay i have replaced n with k but another problem , when i enter -1 my programme exits ?

[ne555]

'k' is out of bounds.

You keep doing the same mistakes over and over again.
Also, liar.

[Maggi Iggam]

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 ?

[ne555]

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.

[Maggi Iggam]

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>
using namespace 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 :)

[ne555]

¿what are the constraints?

[Maggi Iggam]

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]

One question if you don't mind: Why are you doing all those exercises?

[ne555]

The 'k' to be retrieved is fixed. You don't need to sort 'n' numbers.

[Maggi Iggam]

@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 .

[Maggi Iggam]

Any replies @ne555 or @coder777 ?o.O

[ne555]

¿Replies to what? ¿what did you change?
I suppose that you misunderstood, because operating on 1e3 numbers instead of 1e5 is quite a difference