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

Обсуждение задачи 1078. Отрезки

Got AC~
Послано Heng 21 сен 2012 11:54
program ural1078(input,output);
  type node=record x,y:longint;num:longint;end;
  var n,i,j,max,maxi:longint;
    f:array[1..500]of longint;
    c:array[1..500]of longint;
    l:array[1..500]of longint;
    a:array[1..500]of node;
  procedure sort(l,r:longint);
    var i,j:longint;k,temp:node;
    begin
      i:=l;j:=r;k:=a[(l+r)div 2];
      repeat
        while a[i].x>k.x do inc(i);
        while k.x>a[j].x do dec(j);
        if i<=j then begin
          temp:=a[i];
          a[i]:=a[j];
          a[j]:=temp;
          inc(i);dec(j);
        end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
    end;
  procedure print(x:longint);
    begin
      if x=-1 then exit;
      print(c[x]);
      write(a[x].num,' ');
    end;
  begin
    readln(n);
    //if n=0 then writeln(0);
    for i:=1 to n do
      with a[i] do begin
      readln(x,y);num:=i;
    end;
    sort(1,n);
    fillchar(c,sizeof(c),255);
    for i:=1 to n do begin f[i]:=1;l[i]:=0;
      for j:=i-1 downto 1 do
        if (a[i].x<a[j].x)and(a[j].y<a[i].y) //Take Care!!!
           then begin
                  if f[j]+1>f[i]
                     then begin
                       f[i]:=f[j]+1;
                       c[i]:=j;
                     end;
                end;
    end;
    for i:=1 to n do
      if f[i]>max then begin
         maxi:=i;max:=f[i];
      end;
    writeln(max);
    print(maxi);
  end.