![:wink:](./images/smilies/icon_wink.gif)
105 - The Skyline Problem
Moderator: Board moderators
a clarification about 105 skyline problem
for sample input in the problem is I/o is as follows:
How can this be possible
My head has stopped working !!!!!!!!! can anybuddy pls explain
Thanks in advance
Sample Input
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
and my output for the same input sample is :
Sample Output:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
and i got AC
1 11 3 13 9 0 12 7 16 3 19 18 23 13 29 0
![:-?](./images/smilies/icon_confused.gif)
![:roll:](./images/smilies/icon_rolleyes.gif)
Thanks in advance
Time that gone is gone forever ...
This is a problem indeed. Post this problem in the Bugs and suggestions forum.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Hi people. Can you tell me is it possible to get TLE here?? I got!
Please tell me what's wrong with my code, that makes it TLE:
Please tell me what's wrong with my code, that makes it TLE:
Code: Select all
#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
int main(int argc, char *argv[]) {
int i = 0,l[5005],r[5005],h[5005],n;
while (cin >> l[i] >> h[i] >> r[i])
i++;
n = --i;
float x=-0.5;
int ch=0;
while (x<=r[n]+0.5) {
x += 1.0;
int chmax = ch;
for (i=0;i<=n;i++) {
if ((r[i]==floor(x-0.5))&&(h[i]==ch)) {
chmax = 0;
break;
}
}
for (i=0;i<=n;i++) {
if ((l[i] <= floor (x-0.5))&&(r[i] > floor(x-0.5))&&(h[i]>chmax)) {
chmax = h[i];
}
}
if (chmax != ch) {
cout << floor(x-0.5) << " " << chmax << " ";
ch= chmax;
}
}
return EXIT_SUCCESS;
}
Now I lay me down to sleep...
my profile
my profile
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
thanx, rio. BTW, don't you know, is there any way to optimize such an algorithm or I have to think about a new one?
Now I lay me down to sleep...
my profile
my profile
I keep getting WA..
It works for all test cases here...I even tested for L>R and ignored when L=R. The Code works fine...it organizes the builings by its right and left coordenates..and after it, try to draw a line through its height(it saves the heights at a stack of ordered heights) ...
What am I missing here? If a building such as 1 1 1 exists, what should I print? 1 1 1 0? or nothing? thanks
Code: Select all
#include <stdio.h>
#include <stdlib.h>
typedef struct predio{
long int x;
long int y;
struct predio *st;
struct predio *d;
struct predio *e;
}Tpredio;
Tpredio *criaPonto(long int x, long int y, Tpredio *st){
Tpredio *p;
p=(Tpredio*)malloc(sizeof(Tpredio));
(*p).x=x;
(*p).y=y;
(*p).st=st;
(*p).d=NULL;
(*p).e=NULL;
return p;
}
Tpredio* inserePonto(Tpredio *novo,Tpredio *ant, Tpredio *prim){
Tpredio *aux,*aux2;
if ((*novo).x>(*ant).x){
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
} else {
aux=ant;
if ((*novo).x==(*ant).x){
if (((*novo).y)>((*ant).y)){
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
else {
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
}
} else {
while (((*aux).e!=NULL) && ((*novo).x<(*((*aux).e)).x)){
aux=(*aux).e;
}
if (((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)){
if ((*novo).y>(*((*aux).e)).y) {
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
}
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
}
return prim;
}
Tpredio *defineAnt(Tpredio *novo,Tpredio *ant){
if ((*novo).x>(*ant).x)
return novo;
if (((*novo).x==(*ant).x) && ((*novo).y<=(*ant).y))
return novo;
else
return ant;
}
Tpredio *insereLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=NULL; aux=NULL;
if (prim==NULL){
l=criaPonto((*p).x,(*p).y,(*p).st);
return l;
} else {
l=prim;
if ((l!=NULL) && ((*p).y<(*l).y)){
while (((*l).d!=NULL) && ((*p).y)<(*((*l).d)).y){
l=(*l).d;
}
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=(*l).d;
(*l).d=aux;
return prim;
} else {
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=prim;
return aux;
}
}
}
Tpredio *removeLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=prim;
if (l!=NULL){
while (((*l).st!=p) && ((*l).d!=NULL)) {
aux=l;
l=(*l).d;
}
if (((*l).st)==p){
if (l==prim){
aux=(*prim).d;
(*prim).d=NULL;
free(prim);
prim=aux;
} else {
(*aux).d=(*l).d;
(*l).d=NULL;
free(l);
}
}
}
return prim;
}
int main(int argc, char** argv){
long int x1,x2,x3,y,h_max,h_ant,conta,x_prox;
Tpredio *ant,*novo,*prim,*aux,*plista;
conta=0;
novo=NULL;prim=NULL;
while (scanf("%ld %ld %ld",&x1,&y,&x2)!=EOF){
if (x1>x2){
x3=x1;
x1=x2;
x2=x3;
}
if ((x1!=x2) && (y>0)){
if (conta==0){
novo=criaPonto(x1,y,NULL);
ant=novo;
aux=novo;
novo=criaPonto(x2,y,NULL);
prim=aux;
prim=inserePonto(novo,ant,prim);
(*prim).st=novo;
ant=defineAnt(novo,ant);
conta++;
} else {
novo=criaPonto(x1,y,NULL);
prim=inserePonto(novo,ant,prim);
aux=novo;
ant=defineAnt(novo,ant);
novo=criaPonto(x2,y,NULL);
(*aux).st=novo;
prim=inserePonto(novo,ant,prim);
ant=defineAnt(novo,ant);
}}
}
aux=prim;
h_ant=0;
h_max=0;
plista=NULL;
while ((*aux).d!=NULL){
x_prox=(*(*aux).d).x;
if (plista!=NULL)
h_ant=(*plista).y;
else
h_ant=0;
if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);
while (((*aux).d!=NULL)&&(x_prox==(*aux).x)){
aux=(*aux).d;
if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);
if ((*aux).d!=NULL)
x_prox=(*(*aux).d).x;
}
if (plista!=NULL)
h_max=(*plista).y;
else
h_max=0;
if (h_max!=h_ant)
printf("%ld %ld ",(*aux).x,h_max);
if ((*aux).d!=NULL)
aux=(*aux).d;
}
printf("%ld 0\n",(*aux).x);
while ((*aux).e!=NULL){
novo=aux;
aux=(*aux).e;
(*novo).e=NULL;
(*novo).d=NULL;
free(novo);
}
(*aux).e=NULL;
(*aux).d=NULL;
free(aux);
return 0;
}
What am I missing here? If a building such as 1 1 1 exists, what should I print? 1 1 1 0? or nothing? thanks
105 Compile error
I got compile error with cpp.
and i got runtime error with java.
please solve my problem...
two codes are same algorithm...
and i got runtime error with java.
please solve my problem...
two codes are same algorithm...
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
class Node {
public:
int point;
int data;
Node* link;
Node(int point, int data) {
this->point = point;
this->data = data;
this->link = NULL;
}
void print() {
Node *loc = link;
printf("%d %d", &point, &data);
while(loc != NULL) {
printf(" %d %d", loc->point, loc->data);
loc = loc->link;
}
}
};
Node* addNode(Node* list, int start, int height, int end) {
Node *add = new Node(start, height);
Node *loc = list;
Node *prev = NULL;
Node *bprev = NULL;
if(list == NULL) { // Add no element
list = add;
Node* lastnode = new Node(end, 0);
list->link = lastnode;
return list;
}
else if(list->point > start) { // Add first node
Node* lastnode = new Node(start, height);
list = add;
list->link = lastnode;
}
// find add point
while(loc != NULL && loc->point < start) {
bprev = prev;
prev = loc;
loc = loc->link;
}
if(bprev!=NULL) {
}
// loc is equal to start or greater.
if(loc == NULL) { // Last
prev->link = add;
Node* lastnode = new Node(end, 0);
add->link = lastnode;
return list;
}
else if (loc->point == start) { // loc = start
if(loc->data < height) { // loc is less than height
loc->data = height;
}
}
else { // temp != start
if(prev->data < height) { // height is greater than current height
add->link = loc;
prev->link = add;
//Change loc
// loc = add;
bprev = prev;
prev = add;
}
}
while(loc != NULL && loc->point <= end) { // Change mid of start and end
if(loc->data < height) { // current height is less than new height
loc->data = height;
bprev = prev;
prev = loc;
loc = loc->link;
}
else if(loc->data >= height) {// current height is greater than new height
bprev = prev;
prev = loc;
loc = loc->link;
}
}
// End is null
if(loc == NULL) {
Node* lastnode = new Node(end, 0);
prev->link = lastnode;
return list;
}
// end point is less than current end
if (loc->point > end) {
Node* lnode = new Node(end, bprev->data);
prev->link = lnode;
lnode->link = loc;
}
return list;
}
void main()
{
Node* data = NULL;
int start, height, end;
while(scanf("%d %d %d", &start, &height, &end)==3) {
data = addNode(data, start, height, end);
}
data->print();
}
Code: Select all
import java.io.*;
import java.util.*;
class Node {
int point;
int data;
Node link;
Node(int point, int data) {
this.point = point;
this.data = data;
this.link = null;
}
public String toString() {
Node temp = link;
String ret;
ret = Integer.toString(point) + " " + Integer.toString(data);
int bdata = data;
while(temp!=null) {
if(bdata != temp.data)
ret += " " + Integer.toString(temp.point) + " " + Integer.toString(temp.data);
bdata = temp.data;
temp = temp.link;
}
return ret;
}
}
class Sky {
public static Node addNode(Node list, int start, int height, int end) {
Node add = new Node(start, height);
Node loc = list;
Node prev = null;
Node bprev = null;
if(list == null) { // Add no element
list = add;
Node lastnode = new Node(end, 0);
list.link = lastnode;
return list;
}
else if(list.point > start) { // Add first node
Node lastnode = new Node(start, height);
list = add;
list.link = lastnode;
}
// find add point
while(loc != null && loc.point < start) {
bprev = prev;
prev = loc;
loc = loc.link;
}
if(bprev!=null) {
}
// loc is equal to start or greater.
if(loc == null) { // Last
prev.link = add;
Node lastnode = new Node(end, 0);
add.link = lastnode;
return list;
}
else if (loc.point == start) { // loc = start
if(loc.data < height) { // loc is less than height
loc.data = height;
}
}
else { // temp != start
if(prev.data < height) { // height is greater than current height
add.link = loc;
prev.link = add;
//Change loc
// loc = add;
bprev = prev;
prev = add;
}
}
while(loc != null && loc.point <= end) { // Change mid of start and end
if(loc.data < height) { // current height is less than new height
loc.data = height;
bprev = prev;
prev = loc;
loc = loc.link;
}
else if(loc.data >= height) {// current height is greater than new height
bprev = prev;
prev = loc;
loc = loc.link;
}
}
// End is null
if(loc == null) {
Node lastnode = new Node(end, 0);
prev.link = lastnode;
return list;
}
// end point is less than current end
if (loc.point > end) {
Node lnode = new Node(end, bprev.data);
prev.link = lnode;
lnode.link = loc;
}
return list;
}
public static void main(String[] args) {
Node data = null;
try {
while(true) {
Scanner conIn = new Scanner(System.in);
int start, height, end;
start = conIn.nextInt();
height= conIn.nextInt();
end = conIn.nextInt();
data = addNode(data, start, height, end);
conIn = new Scanner(System.in);
}
}
catch (Exception ee) {
System.out.println(data);
}
}
}
When I compile your cpp program I got the following error
Changing in function main: void to int
and header <iostream.h> to <iostream>
I've had succes
Good luck
Code: Select all
c++ pro.cpp -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
In file included from /usr/include/c++/4.1.3/backward/iostream.h:31,
from pro.cpp:3:
/usr/include/c++/4.1.3/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
pro.cpp:114: error: ::main must return int
and header <iostream.h> to <iostream>
I've had succes
Good luck
input limit of 105
105 problem description clearly told about positve integers. and my code replys right outputs due to the possible inputs which i got on net but not for negatve co-ordinates. what i should do?
Like some people said in other threads, I my AC programs gives
1 11 3 13 9 0 12 17 16 3 19 18 22 3 23 29 0
for the test case stated in the problem.
I solved it by printing the x,y coordinates of the corners in the generated image, which isn't what is described by the problem but it gives an accepted solution.
1 11 3 13 9 0 12 17 16 3 19 18 22 3 23 29 0
for the test case stated in the problem.
I solved it by printing the x,y coordinates of the corners in the generated image, which isn't what is described by the problem but it gives an accepted solution.
I've made multiple versions of this, even trying to accomodate for the weird AC that shiggy got, but all get WA. This is the version that should accomodate for everything (gives the same output for the test input provided as the problem lists). I am completely stuck and can't find testcases that give this an answer which doesn't make sense.
Can anyone see anything wrong with the logic there?
Code: Select all
#include <stdio.h>
int top[20001];
int main() {
int a,a1,b,c,maxc=0;
for (int i = 0; i < 20000; i ++) {
top[i] = 0;
}
scanf("%d %d %d",&a1,&b,&c);
for (int i = 2*a1; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;
while (scanf("%d %d %d",&a,&b,&c) != EOF) {
if (c <= a) continue;
for (int i = 2*a; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;
}
printf("%d %d",a1,top[2*a1]);
for (int i = 2*a1+2; i <= 2*maxc; i+=2) {
if (top[i] > top[i+1]) {
printf(" %d %d",i/2,top[i+1]);
} else if (top[i-1] < top[i]) {
printf(" %d %d",i/2,top[i]);
}
}
return 0;
}
105 RE Need help!
I use a 2-D array as a map to record the building block area
then I check the corner coordinate to gain the vector list
I got the same output as the problem statement.
and I checked the array boundary to see if there are any potential illegal reference, however , I found none.
Can anyone help me?
I would really really appreciate that.
Thanks in advance.
The following is my code
Please help me!!!
then I check the corner coordinate to gain the vector list
I got the same output as the problem statement.
and I checked the array boundary to see if there are any potential illegal reference, however , I found none.
Can anyone help me?
I would really really appreciate that.
Thanks in advance.
The following is my code
Code: Select all
#include <stdio.h>
#define MAX 10002
int main(void)
{
int map[MAX][MAX];
int left,height,right;
int limitL,limitH,limitR;
int vector[MAX*2][2];
int vec_count=0;
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[i][j]=0;
/* basement set shadow */
for(i=0;i<MAX;i++)
map[0][i]=1;
limitL = MAX-1;
limitR = 1;
limitH = 1;
/* shadowing */
while( scanf("%d %d %d",&left,&height,&right)==3 )
{
if( left < limitL )
limitL = left;
if( right > limitR )
limitR = right;
if( height > limitH )
limitH = height;
for(i=1;i<=height;i++)
for(j=left;j<right;j++)
{
map[i][j]=1;
}
}
/* printf("%d %d %d\n",limitL,limitH,limitR); */
/* record coordinate into vector array */
for( j=limitL ; j<=limitR ; j++ )
{
i=0;
while( map[i][j] == 1 )
{
i++;
}
vector[vec_count][0]=j;
vector[vec_count][1]=i-1;
vec_count++;
}
/* print vector */
int row = vector[0][1];
printf("%d %d",vector[0][0],vector[0][1]);
for(i=0;i<vec_count;i++)
{
if( vector[i][1] == row )
continue;
row = vector[i][1];
printf(" %d %d",vector[i][0],vector[i][1]);
}
printf("\n");
return 0;
}
-
- New poster
- Posts: 1
- Joined: Fri Mar 14, 2008 2:03 pm
105 Compilation Error
This is my first problem which i think i have solved
Correction Now This gives Runtime Error
I don't have linux so i can't really test this
Also this works in TurboC
#include<stdio.h>
struct dat
{
int x1;
int h;
int x2;
};
void main()
{
struct dat pos[100];
int arr[500];
int i=0,j,k=1,x;
int sbx1,sbx2,sbh,psbh=0;
while(scanf("%d %d %d",&pos.x1,&pos.h,&pos.x2)==3)
i++;
for(x=0;x<100;x++)
arr[x]=0;
arr[0]=sbx1=pos[0].x1;
arr[1]=sbh=pos[0].h;
arr[2]=sbx2=pos[0].x2;
k=3;
for(j=1;j<i;j++)
{
if(pos[j].x1<sbx2)
{
if(pos[j].x1<sbx1)
{
if(pos[j].x2<sbx2)
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=sbh;
arr[k+1]=sbx2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=pos[j].h;
arr[k+1]=sbx2;
}
psbh=pos[j].h;
sbx1=pos[j].x2;
}
}
else
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx2=pos[j].x2;
}
k=k-2;
sbh=pos[j].h;
}
}
}
else
{
if(pos[j].h>sbh)
{
if(pos[j].x2<sbx2)
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
arr[k+2]=sbh;
arr[k+3]=sbx2;
sbx1=pos[j].x2;
psbh=pos[j].h;
k=k+2;
}
else
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
}
else
{
if(pos[j].x2>sbx2)
{
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
sbx1=sbx2;
sbx2=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
}
else k=k-2;
}
}
}
else
{
arr[k]=0;
psbh=0;
arr[k+1]=pos[j].x1;
arr[k+2]=pos[j].h;
arr[k+3]=pos[j].x2;
sbx1=pos[j].x1 ;
sbx2=pos[j].x2;
sbh=pos[j].h;
k=k+2;
}
k=k+2;
}
printf("\nOUTPUT \n");
for(x=0;x<=k;x++)
{
printf(" %d ",arr[x]);
}
}
Correction Now This gives Runtime Error
I don't have linux so i can't really test this
Also this works in TurboC
#include<stdio.h>
struct dat
{
int x1;
int h;
int x2;
};
void main()
{
struct dat pos[100];
int arr[500];
int i=0,j,k=1,x;
int sbx1,sbx2,sbh,psbh=0;
while(scanf("%d %d %d",&pos.x1,&pos.h,&pos.x2)==3)
i++;
for(x=0;x<100;x++)
arr[x]=0;
arr[0]=sbx1=pos[0].x1;
arr[1]=sbh=pos[0].h;
arr[2]=sbx2=pos[0].x2;
k=3;
for(j=1;j<i;j++)
{
if(pos[j].x1<sbx2)
{
if(pos[j].x1<sbx1)
{
if(pos[j].x2<sbx2)
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=sbh;
arr[k+1]=sbx2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=pos[j].h;
arr[k+1]=sbx2;
}
psbh=pos[j].h;
sbx1=pos[j].x2;
}
}
else
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx2=pos[j].x2;
}
k=k-2;
sbh=pos[j].h;
}
}
}
else
{
if(pos[j].h>sbh)
{
if(pos[j].x2<sbx2)
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
arr[k+2]=sbh;
arr[k+3]=sbx2;
sbx1=pos[j].x2;
psbh=pos[j].h;
k=k+2;
}
else
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
}
else
{
if(pos[j].x2>sbx2)
{
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
sbx1=sbx2;
sbx2=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
}
else k=k-2;
}
}
}
else
{
arr[k]=0;
psbh=0;
arr[k+1]=pos[j].x1;
arr[k+2]=pos[j].h;
arr[k+3]=pos[j].x2;
sbx1=pos[j].x1 ;
sbx2=pos[j].x2;
sbh=pos[j].h;
k=k+2;
}
k=k+2;
}
printf("\nOUTPUT \n");
for(x=0;x<=k;x++)
{
printf(" %d ",arr[x]);
}
}