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

Any test data can help me? Always WA..I'm getting crazy! Thx!
Posted by Artanis 27 Jul 2007 20:51
I've tried many test data.But I always got wa on test data 8.

Here is my code.
And I'm sorry for my bad English- -!
Waiting for your data! Thanks very much!


program ural1019_3;
var
  fill:array [1..5000,1..3] of longint;
  point:array [1..10003] of longint;
  col:array [1..10002] of byte;
  a,i,d,n,la,nn,x,y,u,yy:longint;
  c:char;

procedure qsort(l,r:integer);
var i,j,x,y:longint;
begin
     i:=l;j:=r;x:=point[(l+r) div 2];
     repeat
           while point[i]<x do inc(i);
           while point[j]>x do dec(j);
           if i<=j then begin
              y:=point[i];point[i]:=point[j];point[j]:=y;
              inc(i);dec(j);
           end;
     until i>j;
     if l<j then qsort(l,j);
     if i<r then qsort(i,r);
end;

procedure work;
var
  a,i,b,ll,max,lr,ml,mr:longint;

  function x2find(p:longint):integer;
  var a,l,r,x:longint;
  begin
    l:=1;r:=nn;
    while l<r do begin
          x:=point[(l+r) div 2];
          if p=x then break;
          if p<x then r:=(l+r) div 2-1;
          if p>x then l:=(l+r) div 2+1;
    end;
    x2find:=(l+r) div 2;
  end;

begin
  for a:=1 to nn-1 do col[a]:=1;
  for a:=1 to n do begin
      i:=x2find(fill[a,1]);
      for b:=i to nn-1 do if point[b]<>fill[a,2] then col[b]:=fill[a,3] else break;
  end;
  max:=0;a:=1;
  while a<nn do begin
        while (col[a]=2) and (a<=nn-1) do inc(a);
        if a=nn then break;
        ll:=point[a];
        while (col[a]=1) and (a<=nn-1) do inc(a);
        lr:=point[a];
        if lr-ll>max then begin max:=lr-ll; ml:=ll; mr:=lr; end;
  end;
  if n<=0 then writeln('0 1000000000') else writeln(ml,' ',mr);
end;

begin
  readln(n);u:=n;
  for a:=1 to u do begin
      read(x,y,c);
      while (c<>'w') and (c<>'b') do read(c);
      readln;
      if x>y then begin yy:=x; x:=y; y:=yy; end;
      if x=y then begin dec(n); continue; end;
      fill[a,1]:=x; fill[a,2]:=y;
      point[a*2-1]:=fill[a,1];point[a*2]:=fill[a,2];
      if c='w' then fill[a,3]:=1 else fill[a,3]:=2;
  end;
  point[n*2+1]:=0;point[n*2+2]:=1000000000;
  qsort(1,n*2+2);
  la:=1;i:=2;
  while i<n*2+2 do begin
        while (point[i]=point[la]) and (i<=n*2+2) do inc(i);
        if i>n*2+2 then break;
        inc(la);
        point[la]:=point[i];
  end;
  nn:=la;
  work;
end.

Edited by author 27.07.2007 20:54
Re: Any test data can help me? Always WA..I'm getting crazy! Thx!
Posted by Artanis 27 Jul 2007 22:45
O my god.I checked it for 2 hours.Finally I found where I was wrong.

Here is the data which showed me I was wrong.

11
1 999999999 b
5175 8925 b
2844 6891 w
1820 3903 b
8978 8978 b
4663 6345 w
316 1072 w
3197 7933 w
4124 4725 b
2832 3401 w
663 5756 w

Correct answer is:316 7933
Hope it can help you.
And sorry for my terrible English again.

Edited by author 27.07.2007 22:46

Edited by author 31.07.2007 09:56
Re: Any test data can help me? Always WA..I'm getting crazy! Thx!
Posted by Rachel 24 Jul 2008 12:29
a very useful testcase indeed!
Re: Any test data can help me? Always WA..I'm getting crazy! Thx!
Posted by Drenight 16 Apr 2017 21:42
so thx!