105 - The Skyline Problem

[Ovro]

Getting WA. Can someone plz help me?

Code: Select all

#include<stdio.h>
int main()
{
    int a1[20100],a2[20100],h[5100],height,ara[20100],i,count=0,j;
    while((scanf("%d %d %d",&a1[count],&h[count],&a2[count])==3))
        count++;
    for(i=0;i<20100;i++)
        ara[i]=0;
    int k;
    for(k=0;k<count;k++)
    {
        if(a1[k]==a2[k])
            continue;
        for(j=2*a1[k];j<=2*a2[k];j++)
        {
            if(ara[j]<=h[k])
                ara[j]=h[k];
        }
    }
    height=ara[0];
    for(i=0;i<20100;i++)
    {
        if(ara[i]>height)
        {
            height=ara[i];
            printf("%d %d ",i/2,height);
        }
        if(ara[i]<height)
        {
            height=ara[i];
            printf("%d %d ",(i-1)/2,height);
        }
    }
    printf("\b\n");
    return 0;
}

[brianfry713]

Don't print a space or a '\b' at the end of the line.

[Ovro]

Thanks a lot sir. It is AC now.

[just_yousef]

A lot of WA,, Please Help :/

Code: Select all

AC :D

[lbv]

A lot of WA,, Please Help :/

Try reading the previous messages from the forums. For example, brianfry713's post from around Mar 19, 2013 has advice that applies to your code.

[just_yousef]

A lot of WA,, Please Help :/

Try reading the previous messages from the forums. For example, brianfry713's post from around Mar 19, 2013 has advice that applies to your code.

6 WA Only Because Of New line Thanks lbv

[azisak]

Help please, i got WA on this, and i got tired to find where's the failure

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;

int pos[10001]={0};

main()
{
    int l,h,r;
    //freopen("0tes.txt","r",stdin);
    while (cin>>l>>h>>r)
    {
        for (int i=l;i<r;i++){
            if (h>pos[i])
                pos[i]=h;

        }

    }

    bool notfirst=false;
    int hnow=0;
    
    for (int i=0;i<1000;i++)
    {
        if (pos[i]!=hnow)
        {
            if (notfirst)
                cout<<' ';
            else
            notfirst=true;
            cout<<i<<' '<<pos[i];
            hnow=pos[i];
        }
    }
    cout<<endl;

}

[brianfry713]

Change line 25 to:
for (int i=0;i<=10000;i++)

[BD_Star]

Why my code gone failed with verdict Wrong answer. My Source code is following:-

Code: Select all

/* Problem:  105 - "The Skyline Problem" */

#include <iostream>
using namespace std;
 
int	main(){
int	data[10002]; 
int	l,h,r;
int start=1,end=0;
 
for(int	i = 0; i < 10002; i++) data[i] = 0; 

while(cin >> l >> h >> r){
	if(l<=0) l=1;
	for(int	i = l; i < r; i++){
		if(h > data[i]){
			data[i] = h;
			if(i<start){
				start=i;
			}
			if(i>end){
				end=i;
			}
		}
	}
}

int x=start;
cout<<x<<" "<<data[x]<<" ";
for(int i=start;i<=end+1;i++){
	if(data[i]!=data[x]){
		x=i;
		cout<<x<<" "<<data[x]<<" ";
	}
}

return	0; 
}

I have check following input and output

Input #1:
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

Output(for input set #1):
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Input #2:
3 2 4
3 1 7
5 2 6

output(my code output for input set #2):
1 0 3 2 4 1 5 2 6 1 7 0

Also, form http://www.udebug.com/UVa/105
i got output for input set #2
1 0 3 2 4 1 5 2 6 1 7 0

Input #3:
-5 5 1
1 6 2
1 2 7
3 12 10
4 3 5
7 5 20
8 15 12
11 12 13
16 14 19
21 2 22
23 1 30
26 10 28
26 12 27
32 5 36
34 3 38
34 3 40
37 2 42
38 2 44
45 1 46

output
1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0 <=[my code output for input #3]
1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0 <=[output from http://www.udebug.com/UVa/105]

So what is the problem??? For what types of input it got WA? Or give me some critical input.
Please anyone help me

[brianfry713]

Print a newline char at the end of the line. Don't print a space at the end of the line

[4dummies]

I finally got accepted. I used a max-heap to keep track of the highest current building, along with its end x. At each event, I discard any tall buildings that are past x; what's left on top of the heap is the tallest.

This way the algorithm only looks at actual start and ending x values. I wanted working heap code anyway, so I'm happy.