|
|
back to boardGot AC~ Posted by Heng 21 Sep 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. |
|
|