Discussion @ 1019. Line Painting @ Timus Online Judge

Give me some test, please!I got WA!

Posted by Algorithmus_UA(algorithmus@univ.kiev.ua) 14 Jun 2002 16:17

Re: Give me some test, please!I got WA!

Posted by Ivan Georgiev 16 Jun 2002 15:50

look at this test
2
33 99 w
21 91 b

your program prints 99 1000000000
but the answer obviously is 91 1000000000

good luck.

Thank's I check this bug, but I gov WA again!

Posted by Algorithmus_UA(algorithmus@univ.kiev.ua) 17 Jun 2002 14:21

const MAXN = 5005;
type
pointtype = record
               x:longint;
               y:integer;
{               b:byte;}
             end;

var a:array[0..MAXN*2]of pointtype;
    b:array[1..MAXN]of integer;
    ccc:array[1..MAXN]of integer;
    s:array[1..MAXN]of integer;
    r:array[1..MAXN]of integer;
    N,i,h:integer;ch:char;
    col:integer;
    max,c,ai,bi,x,l:longint;
procedure sort(l,r: integer);
var
i,j: integer;y:pointtype;x:longint;
begin
i:=l; j:=r; x:=a[(l+r) DIV 2].x;
repeat
    while a[i].x<x do i:=i+1;
    while x<a[j].x do j:=j-1;
    if i<=j then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1;
    end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure uph(k:integer);
var v:integer;
begin
if 2*k+1<=h then
begin
    if s[2*k+1]>s[2*k] then v:=2*k+1 else v:=2*k;
    if s[v]>s[k] then
    begin
      c:=s[v];s[v]:=s[k];s[k]:=c;
      r[s[v]]:=v;r[s[k]]:=k;
      if k div 2 <>0 then uph(k div 2);
    end;
end
else if 2*k<=h then
begin
    v:=2*k;
    if s[v]>s[k] then
    begin
      c:=s[v];s[v]:=s[k];s[k]:=c;
      r[s[v]]:=v;r[s[k]]:=k;
      if k div 2 <>0 then uph(k div 2);
    end;
end;
end;

procedure downh(k:integer);
var v:integer;
begin
if 2*k+1<=h then
begin
    if s[2*k+1]>s[2*k] then v:=2*k+1 else v:=2*k;
    if s[v]>s[k] then
    begin
      c:=s[v];s[v]:=s[k];s[k]:=c;
      r[s[v]]:=v;r[s[k]]:=k;
      downh(v);
    end;
end
else if 2*k<=h then
begin
    v:=2*k;
    if s[v]>s[k] then
    begin
      c:=s[v];s[v]:=s[k];s[k]:=c;
      r[s[v]]:=v;r[s[k]]:=k;
      downh(v);
    end;
end;
end;

begin
readln(N);
for i:=1 to N do
begin
   read(ai,bi);read(ch);read(ch);readln;
   a[2*i].x:=ai;
   a[2*i-1].x:=bi;
   a[2*i].y:=i;
   a[2*i-1].y:=i;
   if ch = 'b' then
   begin
     ccc[i]:=1;
   end
   else
   begin
     ccc[i]:=0;
   end;
end;
{ inc(N);
a[2*N].a:=0;a[2*N-1].a:=1000000000;
a[2*N].b:=N;a[2*N-1].b:=N;
a[2*N].c:=0;a[2*N-1].c:=0;}
sort(1,2*N);
x:=a[1].x;col:=0;
max:=x;
l:=0;
for i:=1 to 2*N-1 do
begin
   if b[a[i].y]=0 then
   begin
     inc(h);
     r[a[i].y]:=h;
     s[h]:=a[i].y;
     if h div 2<>0 then uph(h div 2);
     b[a[i].y]:=1;
   end
   else
   begin
     s[r[a[i].y]]:=s[h];dec(h);
     downh(r[a[i].y]);
     r[a[i].y]:=0;
   end;
   if ccc[s[1]] = col then
   begin
     x:=x+a[i+1].x-a[i].x;
     if (col = 0)and(x>max) then
     begin
       max:=x;
       l:=a[i+1].x-x;
     end;
   end
   else
   begin
     if a[i+1].x-a[i].x<>0 then
     begin
       x:=a[i+1].x-a[i].x;
       col:=ccc[s[1]];
       if (col = 0)and(x>max) then
       begin
         max:=x;
         l:=a[i+1].x-x;
       end;
     end;
   end;
end;
if 1000000000-a[2*n].x>max then
begin
   max:=1000000000-a[2*n].x;
   l:=a[2*n].x;
end;
if col = 0 then
begin
   x:=x+1000000000-a[2*n].x;
   if x>max then
   begin
     max:=x;
     l:=1000000000-x;
   end;
end;
writeln(l,' ',l+max);
end.

Re: Thank's I check this bug, but I gov WA again!

Posted by Ivan Georgiev 18 Jun 2002 02:05

look at this test
10
1 999999999 b
234 543 w
26 345 w
522 5453 w
64 345 b
384 400 b
774 1000 w
888 999 b
777 888 b
1 10 b

you print 999 1000000000
but the answer is 999 5453

good luck.

Thank you very much!!!! Now I AC this problem!!!

Posted by Algorithmus_UA(algorithmus@univ.kiev.ua) 19 Jun 2002 17:40

Discussion of Problem 1019. Line Painting