ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1019. Перекрашивание прямой

Please give me some tests,
Послано Cancer 25 дек 2002 20:39

COnst
  max=5000;
Type
  arr=array[1..Max] of longint;
Var
  mi,mj,ni,nj:longint;
  temp:longint;
  now,maxn:longint;
  m:array[-1..Max*4] of boolean;
  c:array[1..Max] of boolean;
  Left,Right,x,y,L,r:arr;
  s:array[-1..Max*4] of longint;
  i,j,k,p,pl,pr,n:longint;
  ch:char;
Procedure Order(var a,b:arr);
  Var
    c:arr;
  begin
    for i:=1 to n do
    c[i]:=i;
    for i:=1 to n do
      for j:=i+1 to n do
        if a[c[i]]>a[c[j]] then
          begin
            temp:=c[i];
            c[i]:=c[j];
            c[j]:=temp;
          end;
    for i:=1 to n do
       b[i]:=a[c[i]];
    for i:=1 to n do
      a[c[i]]:=i;
  end;

Procedure Init;
Begin

  readln(n);
  for i:=1 to n do
  begin
    read(x[i],y[i]);
     if x[i]>y[i] then
      begin
        temp:=x[i];
        x[i]:=y[i];
        y[i]:=temp;
      end;
    repeat
      read(ch);
    until ch in['b','w'];
    c[i]:=(ch='w');
  end;
  Left:=x;
  Right:=y;
  Order(Left,L);
  Order(Right,r);
  pl:=1;
  pr:=1;
  p:=1;
  s[1]:=1;
  while (pl<=n)and(pr<=n) do
    begin
      if l[pl]<r[pr] then
        begin
          if l[pl]-1>s[p] then
            begin
              inc(p);
              s[p]:=l[pl]-1;
            end;
          if l[pl]>s[p] then
          begin
          inc(p);
          s[p]:=l[pl];
          end;
          l[pl]:=p;
          inc(pl);
        end else
      if l[pl]>r[pr] then
        begin
          if r[pr]>s[p] then
          begin
          inc(p);
          s[p]:=r[pr];
          end;
          inc(p);
          s[p]:=r[pr]+1;
          r[pr]:=p-1;
          inc(pr);
        end else
        begin
          if s[p]<l[pl]-1 then
            begin
              inc(p);
              s[p]:=l[pl]-1;
            end;
          if s[p]<l[pl] then
          begin
          inc(p);
          s[p]:=l[pl];
          end;
          inc(p);
          s[p]:=r[pr]+1;
          l[pl]:=p-1;
          r[pr]:=p-1;
          inc(pl);
          inc(pr);
        end;
    end;

  if pl<=n then
    begin
      while (pl<=n)and(l[pl]=s[p]) do inc(pl);
      for i:=pl to n do
        begin
          if l[i]-1>s[p] then
            begin
              inc(p);
              s[p]:=l[i]-1;
            end;
          inc(p);
          s[p]:=l[i];
          l[i]:=p;
        end;
    end  else

  if pr<=n then
    begin
      while (pr<=n)and(r[pr]=s[p]) do inc(pr);
      for i:=pr to n do
        begin
          inc(p);
          s[p]:=r[i];
          inc(p);
          s[p]:=r[i]+1;
          r[i]:=p-1;
        end;
    end;
  if s[p]<>1000000000 then
   begin
     inc(p);
     s[p]:=1000000000;
   end;
  for i:=1 to n do
   begin
    left[i]:=l[left[i]];
    right[i]:=r[right[i]];
   end;
End;

Begin
  Init;
  fillchar(m,sizeof(m),true);
  m[0]:=TRUE;
  s[0]:=0;
  m[-1]:=FALSE;
  S[-1]:=0;

  for i:=1 to n do
    for j:=left[i] to right[i] do
      m[j]:=c[i];

  Maxn:=0;mi:=0;mj:=0;
  now:=0;ni:=0;
  for i:=0 to p do
    if m[i] then

       if m[i-1]
          then
            inc(now,s[i]-s[i-1])
          else
            begin
              now:=1;
              ni:=i;
            end
          else
      if now>maxn then
        begin
          maxn:=now;
          mi:=ni;
          mj:=i-1;
        end;
  if now>maxn then
   begin
      maxn:=now;
      mi:=ni;
      mj:=p;
   end;
  if s[mi]<>0 then dec(s[mi]);
  writeln(s[mi],' ',s[mj]);
End.
Here it is
Послано Ural_Banyan Tree 19 янв 2003 10:18
This input:
4
1 1000000000 b
3 10 w
20 30 w
5 25 w
Your answer is wrong.
Mabye your program can help me!?