105 - The Skyline Problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm

Post by Olorin »

Thanks, Fresh.
Someone else actually suggested that the code as it is now should work great for submission to the Online Judge. So, I'll try it as-is.

Thanks anyway!
-- Elen Sila Lumenn' Omentielvo --
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

you can also try

Post by epsilon0 »

this works on Linux:

when you're done entering your data, press Control-D (EOF)
junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

And in DOS, you can use Ctrl+Z or F6 to get the EOF character
Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

[105] Stupid Judge

Post by Chung Ha, Yun »

I accepted SkyLine Problem.

But, I find that my solution is wrong.

Test case,

3 2 4
3 1 7
5 2 6

Exactly output is

3 2 4 1 5 2 6 1 7 0

But, Judge Server accept follow output.

3 2 6 1 7 0

Hm....
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

My AC program accepts

Code: Select all

3 2 4 1 5 2 6 1 7 0
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

105 - WA?? :(

Post by minskcity »

My code solves example and two other inputs from forum correctly, but I still get WA from judge. Can anyone provide me with more inputs and correct outputs for them? Here is my code (just in case you wonna test it, because it's unreadble):

[cpp]#include <iostream.h>
#include <stdlib.h>
#include <conio.h>

int left[5000];
int right[5000];
int highth[5000];

struct my_str{
int h;
int pos;
char lr;
};

int sort_function( const void *a, const void *b){
if(((my_str *)a)->pos - ((my_str *)b)->pos == 0)
if(((my_str *)a)->lr == 'r'){
return 1;
} else return -1;
return ((my_str *)a)->pos - ((my_str *)b)->pos;
}


int main(){
int n = 0;
while(cin >> left[n] >> highth[n] >> right[n]) n++;

my_str *data = new my_str[n*2];
int *log = new int[n];
int log_size = 0;

int k = 0;
for(int i = 0; i < n; i++){
data[k].h = highth;
data[k].lr = 'l';
data[k].pos = left;
k++;
data[k].h = highth;
data[k].lr = 'r';
data[k].pos = right;
k++;
}

qsort((void *)data, n*2, sizeof(data[0]), &sort_function);

int now = 0;
int temp;

for(int i = 0; i < n*2; i++){
if(data.lr == 'l'){
if(data.h > now){
log[log_size] = data.h;
log_size++;
now = log[log_size - 1];
cout << data.pos << " " << data.h << " ";
} else{
temp = 0;
while(log[temp] < data.h) temp++;
for(int j = log_size; j > temp; j--) log[j] = log[j - 1];
log[temp] = data[i].h;
log_size++;
}
} if(data[i].lr == 'r'){
if(data[i].h == now){
log_size--;
if(log_size == 0){
now = 0;
cout << data[i].pos << " " << 0 << " ";
}else if(log[log_size - 1] < now){
now = log[log_size - 1];
cout << data[i].pos << " " << log[log_size - 1] << " ";
}
} else{
temp = 0;
while(log[temp] != data[i].h) temp++;
log_size--;
for(int j = temp; j < log_size; j++) log[j] = log[j + 1];
}
}
}
getch();
return 0;
}[/cpp]
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

I don't need help on this problem any more. My new program (written in 7 minutes) was accepted. :lol:

[cpp]#include <iostream.h>
int data[10002];
int main(){
int l,h,r;
for(int i = 0; i < 10002; i++) data = 0;

while(cin >> l >> h >> r)
for(int i = l; i < r; i++)
if(h > data) data = h;

for(int i = 0; i < 10001; i++){
if(data < data[i + 1]) cout << (i + 1) << " " << data[i + 1] << " ";
if(data > data[i + 1]) cout << (i + 1) << " " << data[i + 1] << " ";
}
return 0;
}[/cpp]

Sometimes I'm so stupid... :lol:
kenken
New poster
Posts: 4
Joined: Thu Nov 15, 2001 2:00 am
Contact:

105-skyline problem~! COMPILE ERROR!!!

Post by kenken »

ARGG~~~~i have tried 8 time to submit my code, same result COMPILE ERROR~!~! Could anyone show me where is wrong?

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.


[cpp]@begin_of_source_code
/* @JUDGE_ID: 15906YA 105 C++ */
#include <iostream>
using namespace std;
int main ()
{
int array[5001] = {0};
int lef, hi, rite;

while (cin >> lef >> hi >> rite){
int count = rite - lef;
for (int c = 1; c <= count; c++){
if (array[lef] < hi)
array[lef++] = hi;
else
lef++;
}
}

int n = 0;
while (array[++n] == 0){
}
cout << n << " " << array[n] << " ";
int number = n;

for (; number < 4999; number++)
if (array[number] != array[number + 1])
cout << (number + 1) << " " << array[number + 1] << " ";

int x; cin >> x;

return 0;

}
@end_of_source_code[/cpp]
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le »

It is a simple question.
All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file.
Though in the file it said all input should less than but I set to 10000
then got AC.

I have changed your programme that got AC but P.E.

Your should carefully look the problem again that will got AC.

Here is your code with my changed.

[cpp]#include <iostream>

using namespace std;

int main ()
{
int array[10000] = {0};
int lef, hi, rite;

while (cin >> lef >> hi >> rite){
int count = rite - lef;
for (int c = 1; c <= count; c++){
if (array[lef] < hi)
array[lef++] = hi;
else
lef++;
}
}

int n = 0;
while (array[++n] == 0){
}
cout << n << " " << array[n] << " ";
int number = n;

for (; number < 9999; number++)
if (array[number] != array[number + 1])
cout << (number + 1) << " " << array[number + 1] << " ";

int x; cin >> x;

return 0;
} [/cpp]
Pibben
New poster
Posts: 3
Joined: Sat Jun 14, 2003 9:45 am

105 - Unseen trouble?

Post by Pibben »

My code for problem 105 works fine for all tests I've done, but still gets WA by the Judge. Are there any evil special cases I might have missed?

May the data contain buildings with leftcoordinade == rightcoordinate?
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le »

Yes, such as
input output
1 1 1
5 5 6
and so on
yan8381
New poster
Posts: 4
Joined: Wed Nov 26, 2003 4:05 pm

105 skyline problem

Post by yan8381 »

is it possible that left coordinator equal to right coordinator(ie, L==R) for the input data?!? :o

but, now the building is not an rectangular, it is just a line!
secret-mission
New poster
Posts: 4
Joined: Tue Jul 29, 2003 10:56 am

p105 (TSP) - Pascal - WA - Tested [Unsolved]

Post by secret-mission »

I have submited a lot of code for this problem but i still got WA. Any idea? I have read all of the topic before.

[pascal]
(* @begin_of_source_code *)
program p105(input,output);
{$IFDEF ONLINE_JUDGE}
type tint = integer;
{$ELSE}
type tint = longint;
var input : text;
{$IFDEF FILE}
var output : text;
{$ENDIF}
{$ENDIF}
type
tdata = array[1..20001,1..102,1..4] of tint;
var
data : tdata;
i,j,k,l,m,cur,last,max,save,save2 : tint;
s : boolean;
procedure qsort(cur,l,r:tint);
var
i,j,x: tint;
begin
i:=l; j:=r; x:=data[cur,(l+r) DIV 2,2];
repeat
while x<data[cur,i,2] do inc(i);
while data[cur,j,2]<x do dec(j);
if i<=j then
begin
data[cur,102] := data[cur,i];
data[cur,i] := data[cur,j];
data[cur,j] := data[cur,102];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(cur,l,j);
if i<r then qsort(cur,i,r);
end;
procedure qsort2(l,r:tint);
var
i,j,x: tint;
begin
i:=l; j:=r; x:=data[(l+r) DIV 2,1,1];
repeat
while data[i,1,1]<x do inc(i);
while x<data[j,1,1] do dec(j);
if (i<=j) then
begin
data[20001] := data;
data := data[j];
data[j] := data[20001];
inc(i);
dec(j);
end
until i>j;
if l<j then qsort2(l,j);
if i<r then qsort2(i,r);
end;
begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'p105.in');
reset(input);
{$IFDEF FILE}
assign(output,'p105.out');
rewrite(output);
{$ENDIF}
{$ENDIF}
cur := 0;
for l := 1 to 20000 do data[l,101,1] := 1;
while not eof(input) do
begin
read(input,i);
read(input,k);
readln(input,j);
if i <> j then
begin
s := false;
if cur <> 0 then for l := 1 to cur do if i = data[l,1,1] then
begin
s := true;
break;
end;
if not s then
begin
inc(cur);
l := cur;
end;
m := data[l,101,1];
data[l,m,1] := i;
data[l,m,2] := k;
data[l,m,3] := 1;
data[l,m,4] := j;
inc(data[l,101,1]);
s := false;
if cur <> 0 then for l := 1 to cur do if j = data[l,1,1] then
begin
s := true;
break;
end;
if not s then
begin
inc(cur);
l := cur;
end;
m := data[l,101,1];
data[l,m,1] := j;
data[l,m,2] := k;
data[l,m,3] := 2;
data[l,m,4] := i;
inc(data[l,101,1]);
end;
end;
for i := 1 to cur do qsort(i,1,data[i,101,1]-1);
qsort2(1,cur);
{for i := 1 to cur do
begin
for j := 1 to data[i,101,1]-1 do
begin
writeln(i,' ',j,' ',data[i,j,1],' ',data[i,j,2],' ',data[i,j,3],' ',data[i,j,4]);
end;
end;}
last := 0;
save := 0;
for i := 1 to cur do
begin
if data[i,1,3] = 1 then
begin
if data[i,1,2] > last then
begin
if save <> 0 then
begin
write(output,save,' ',save2,' ');
save := 0;
save2 := 0;
end;
write(output,data[i,1,1],' ',data[i,1,2],' ');
last := data[i,1,2];
end;
end
else if data[i,1,3] = 2 then
begin
if (data[i,1,2] = last) and (last <> 0) then
begin
max := 0;
for j := i downto 1 do for k := 1 to data[j,101,1] do if data[j,k,3] = 1 then if (data[j,k,4] > data[i,1,1]) and (data[j,k,2] > max) then max := data[j,k,2];
if max <> last then
begin
if max <> 0 then write(output,data[i,1,1],' ',max,' ')
else
begin
save := data[i,1,1];
save2 := max;
end;
last := max;
end;
end;
end;
end;
if save <> 0 then write(output,save,' ',save2);
writeln;
{$IFNDEF ONLINE_JUDGE}
{$IFDEF FILE}
close(output);
{$ENDIF}
close(input);
{$ENDIF}
end.
(* @end_of_source_code *)
[/pascal]


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




output

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0




input

-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

-5 5 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




input

3 2 4
3 1 7
5 2 6




output

3 2 4 1 5 2 6 1 7 0



I don't know why WA. I hope to hear your idea as soon as possible. Thanks.

Best Regards.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

In the problem it is written that the buildings are rectangular. So hopefully in the judge' data they are rectangular.

But, a good algorithm will automatically take care of this problem.
:)
RyanCHEN
New poster
Posts: 2
Joined: Thu Dec 04, 2003 6:05 pm

why??help me,please!! 105

Post by RyanCHEN »

The compiler couldn't compile your ANSI C/C++ or GNU Pascal/Java program.

[Notes: - Select C, C++, JAVA or PASCAL in the @JUDGE_ID field, to ensure that
I'll use the proper compiler. Place a 'program...' sentence in Pascal.
Note that entry point in Java is a 'main' function in a 'Main' class.
- Do not use more than 1024 characters per line, or 40,000 bytes per
program, if you are submitting your programs by E-Mail.
- Do not use '//' comments except in C++ programs [And Note that this
is not Borland C or Turbo Pascal!].
- Some mail tools reformat your text or the standard mail headers.
I compiled the lines I resent you in the "Program Received" message.
(if your mail system adds extra lines to your letter, please include
a "@end_of_source_code" string after the last source code line).

Here are the compiler error messages:

02121089_24.c: In function `int main()':
02121089_24.c:19: no matching function for call to `vector<int,allocator<int>
>::at (int &)'
02121089_24.c:20: no matching function for call to `vector<int,allocator<int>
>::at (int &)'
02121089_24.c:26: no matching function for call to `vector<int,allocator<int>
>::at (int &)'
02121089_24.c:26: no matching function for call to `vector<int,allocator<int>
>::at (int)'
02121089_24.c:27: no matching function for call to `vector<int,allocator<int>
>::at (int &)'


:evil:
my code is:
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdlib>
using namespace std;

int main()
{
int left,high,right;
ifstream input("input.txt");
vector<int> temp(500,0);
int i;
while(!input.eof())
{
input>>left>>high>>right;
for(i=left;i<right;i++)
{
if(temp.at(i)<high)
temp.at(i)=high;
}

}
for(i=1;i<500;i++)
{
if(temp.at(i)!=temp.at(i-1))
cout<<i<<" "<<temp.at(i)<<" ";
}
return 0;
}
Post Reply

Return to “Volume 1 (100-199)”