105 - The Skyline Problem

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

[epsilon0]

this works on Linux:

when you're done entering your data, press Control-D (EOF)

[junjieliang]

And in DOS, you can use Ctrl+Z or F6 to get the EOF character

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

My AC program accepts

Code: Select all

3 2 4 1 5 2 6 1 7 0

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

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

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

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

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]

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]

Yes, such as
input output
1 1 1
5 5 6
and so on

[yan8381]

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

but, now the building is not an rectangular, it is just a line!

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

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]

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 &)'



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;
}