ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
for a:=1 to u do begin
while (c<>'w') and (c<>'b') do read(c);
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