ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1019. Line Painting

Algorithmus_UA(algorithmus@univ.kiev.ua) Give me some test, please!I got WA! [4] // Problem 1019. Line Painting 14 Jun 2002 16:17
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 byte;
    ccc:array[1..MAXN]of byte;
    s:array[1..MAXN]of integer;
    r:array[1..MAXN]of integer;
    N,i,h:integer;ch:char;
    col:byte;
    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
{ assign(input,'1019.dat');reset(input);}
 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 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;
 writeln(l,' ',l+max);
end.
Ivan Georgiev Re: Give me some test, please!I got WA! [3] // Problem 1019. Line Painting 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.
Algorithmus_UA(algorithmus@univ.kiev.ua) Thank's I check this bug, but I gov WA again! [2] // Problem 1019. Line Painting 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.
Ivan Georgiev Re: Thank's I check this bug, but I gov WA again! [1] // Problem 1019. Line Painting 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.
Algorithmus_UA(algorithmus@univ.kiev.ua) Thank you very much!!!! Now I AC this problem!!! // Problem 1019. Line Painting 19 Jun 2002 17:40