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

Обсуждение задачи 1105. Раскраска наблюдателей

Why i got WA?
Послано Koala 22 авг 2003 17:41
i think i've known the algorithm.
but why wa?

program p1105;

const
  maxn=10000;
  zero=0;

var
  a,b:array [1..maxn] of real;
  code,t:array [1..maxn] of longint;
  n,i,top:longint;
  time,start,finish:real;

  procedure qksort(p,q:longint);
  var
    r,kcode,i,j:longint;
    ka,kb:real;
  begin
    r:=random(q-p+1)+p;
    ka:=a[r]; kb:=b[r]; kcode:=code[r];
    a[r]:=a[p]; b[r]:=b[p]; code[r]:=code[p];
    i:=p; j:=q;
    while i<j do
    begin
      while (i<j) and ((ka<a[j]-zero) or (ka<=a[j]+zero) and (kb>=b
[j]-zero))
        do dec(j);
      a[i]:=a[j]; b[i]:=b[j]; code[i]:=code[j];
      while (i<j) and ((a[i]<ka-zero) or (a[i]<=ka+zero) and (b[i]
>=kb-zero))
        do inc(i);
      a[j]:=a[i]; b[j]:=b[i]; code[j]:=code[i];
    end;
    a[i]:=ka; b[i]:=kb; code[i]:=kcode;
    if p<i-1 then qksort(p,i-1);
    if i+1<q then qksort(i+1,q);
  end;

begin
  read(start,finish);
  read(n);
  for i:=1 to n do
  begin
    read(a[i],b[i]);
    code[i]:=i;
  end;

  if n=0 then
  begin
    writeln(0);
    exit;
  end;

  qksort(1,n);
  t[1]:=1; top:=1;
  for i:=2 to n do
    if b[i]>b[t[top]]+zero then
    begin
      inc(top);
      t[top]:=i;
    end;

  time:=0;
  for i:=1 to top do
    if odd(i) then time:=time+b[t[i]]-a[t[i]];
  if time>=2/3*(finish-start) then
  begin
    writeln((top+1) div 2);
    for i:=1 to top do
      if odd(i) then writeln(code[t[i]]);
    exit;
  end;

  time:=0;
  for i:=1 to top do
    if not(odd(i)) then time:=time+b[t[i]]-a[t[i]];
  if time>=2/3*(finish-start) then
  begin
    writeln(top div 2);
    for i:=1 to top do
      if not(odd(i)) then writeln(code[t[i]]);
    exit;
  end;

  writeln(top);
  for i:=1 to top do writeln(code[t[i]]);
end.
There is a small mistake in it. Now i've got AC.
Послано Koala 23 авг 2003 16:16