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

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

Edric Mao Why i WA2?? // Задача 1105. Раскраска наблюдателей 23 авг 2010 16:02
program ural;
var f,e,p,q:real;
    i,n,s,l,d,t:integer;
    a,b:array[1..10000]of real;
    u,k:array[1..10000]of integer;
    o:array[0..1]of real;
procedure heap;
  begin
    p:=a[s];
    q:=b[s];
    t:=k[s];
    d:=s shl 1;
    if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then
      inc(d);
    while(d<=l)and((p<a[d])or((p=a[d])and(q>b[d])))do
      begin
        a[s]:=a[d];
        b[s]:=b[d];
        k[s]:=k[d];
        s:=d;
        d:=s shl 1;
        if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then
          inc(d);
      end;
    a[s]:=p;
    b[s]:=q;
    k[s]:=t;
  end;
begin
  assign(input,'observe.in');
  assign(output,'observe.out');
  reset(input);
  rewrite(output);
  readln(f,e);
  readln(n);
  for i:=1 to n do
    begin
      k[i]:=i;
      readln(a[i],b[i]);
    end;
  l:=n;
  for i:=n shr 1 downto 1 do
    begin
      s:=i;
      heap;
    end;
  for i:=n downto 2 do
    begin
      t:=k[i];
      k[i]:=k[1];
      k[1]:=t;
      p:=a[i];
      a[i]:=a[1];
      a[1]:=p;
      p:=b[i];
      b[i]:=b[1];
      b[1]:=p;
      s:=1;
      l:=i-1;
      heap;
    end;
  u[1]:=1;
  t:=1;
  for i:=2 to n do
    if b[u[t]]<b[i] then
      begin
        while(t>1)and(a[i]<=b[u[t-1]])do
          dec(t);
        inc(t);
        u[t]:=i;
      end;
  for i:=1 to t do
    o[i and 1]:=b[u[i]]-a[u[i]];
  f:=(e-f)*2/3;
  if o[1]>=f then
    begin
      t:=(t+1) shr 1;
      writeln(t);
      for i:=0 to t-1 do
        writeln(k[u[i shl 1 or 1]]);
    end
  else
    if o[0]>=f then
      begin
        t:=t shr 1;
        writeln(t);
        for i:=1 to t do
          writeln(k[u[i shl 1]]);
      end
    else
      begin
        writeln(t);
        for i:=1 to t do
          writeln(k[u[i]]);
      end;
end.