Moderator: Board moderators

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

### to valfiros

there exist priority queue implemented in STL ???

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

### thanks Emilio

but one more isssue: implementing it using heap has no more advantage than this one, in speed or whatever ??

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
The STL priority_queue is implemented as a heap in a vector<T>.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Are there any trick cases? I also used a heap implementation..

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Nevermind, I missed the N=0 for ending.. I'm an idiot.

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

I don't know why I got WA...

Code: Select all

``````#include<stdio.h>
int n,all,que[5002];
{
int index;
index=all;
all++;
while(index>0)
{
if(in<que[(index-1)/2])
{
que[index]=que[(index-1)/2];
index=(index-1)/2;
}
else
break;
}
que[index]=in;
return 0;
}
int del()
{
int index=0;
all--;
while(index<=(all-2)/2)
{
if(que[all]>que[index*2+1])
{
que[index]=que[index*2+1];
index=index*2+1;
}
else if(index*2+3<=all && que[all]>que[index*2+2])
{
que[index]=que[index*2+2];
index=index*2+2;
}
else
break;
}
que[index]=que[all];
return 0;
}
int main()
{
int k,i,out;
while(scanf("%d",&n)==1 && n!=0)
{
all=out=0;
for(i=0;i<n;i++)
{
scanf("%d",&k);
}
while(all>1)
{
k=que[0];
del();
k+=que[0];
del();
out+=k;
}
printf("%d\n",out);
}
return 0;
}
``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10954 WA

Try this input:

Code: Select all

``````14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
0``````
My AC's output is:

Code: Select all

``717``

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm
Thanks~
I got AC...

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
I'm getting WA using priority queue (and long long data type)

My Input:

Code: Select all

``````5
2 2 2 2 3
5
1 1 1 1 1
14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
4
1 2 3 4
5
1 2 3 4 5
2
1 1
0
``````
My Output:

Code: Select all

``````26
12
717
19
33
2
``````
These are right, I think. Somebody, give me some more I/O, plz...
Thanks...

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
OK, Noboby is giving me some I/O that i wanted in another mail.

Now, would you just plz run my code, and say where I'm wrong!!!

Btw, I did not want to send my code. But, no way....

Code: Select all

``````Code removed after AC
``````
It matches the above test case and many other that I imagine.
Last edited by Nazmul Quader Zinnuree on Sun Aug 27, 2006 1:36 am, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Nazmul Quader Zinnuree wrote:OK, Noboby is giving me some I/O that i wanted in another mail.

Now, would you just plz run my code, and say where I'm wrong!!!
Not working for this one:

Code: Select all

``````8
40952 13521 6223 42589 93489 22376 78730 38792
0``````
My AC's output:

Code: Select all

``899661``

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Code: Select all

``````26
12
717
19
33
2
``````
Yes, this output is correct... In the other thread (where you've posted your code) I've just posted a case your code doesn't work on.

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
The bug was in my extract_min() function. AC now.
Thanks to Martin Macko

tom76925
New poster
Posts: 2
Joined: Tue Aug 12, 2008 3:56 am

### Re: 10954 - Add All

I couldn't find out what's wrong in my code
I test all the data above and the answer was correct
but when I submit on UVa I got WA
could anyone can help me please... thank you very much~

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void createheap(int[],int num);
void heapsort(int[],int num);

int main(void) {
int number[5000+1],ans[5000+1]={0};

scanf("%d",&num);
while(num!=0){
for(i=1;i<=num;i++){
scanf("%d",&number[i]);
}

createheap(number,num);

m=num;
k=1;
while(m>1){

SWAP(number[1], number[m]);
count[0]=number[m];
m--;
heapsort(number,m);

SWAP(number[1], number[m]);
count[1]=number[m];
m--;
heapsort(number,m);

count[2]=count[0]+count[1];
ans[k]=count[2];
k++;

m++;
}

i=1;
while(ans[i]!=0){
i++;
}
scanf("%d",&num);
}
return 0;
}

void createheap(int number[],int num) {
int i, s, p;
int heap[5000+1] = {0};

for(i = 1; i <= num; i++) {
heap[i] = number[i];
s = i;
p = i / 2;
while(s >= 2 && heap[p] > heap[s]) {
SWAP(heap[p], heap[s]);
s = p;
p = s / 2;
}
}

for(i = 1; i <= num; i++)
number[i] = heap[i];

}

int s, p;

s = num;
p = num / 2;
while(s >= 2 && number[p] > number[s]) {
SWAP(number[p], number[s]);
s = p;
p = s / 2;
}
}

void heapsort(int number[],int num) {
int p, s;

p = 1;
s = 2 * p;
while(s <= num) {
if(s < num && number[s+1] < number[s])
s++;
if(number[p] <= number[s])
break;
SWAP(number[p], number[s]);
p = s;
s = 2 * p;
}
}
``````