比赛 20120706 评测结果 AAAAAAAAAA
题目名称 校草 最终得分 100
用户昵称 IMSL77 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2012-07-06 11:56:19
显示代码纯文本
program main;
type
  integer=longint;
const
  maxn=110000;
var
  n,m:integer;
  a:array[1..maxn,1..4] of integer;
  fall:array[1..maxn] of boolean;
  b:array[1..maxn] of integer;
  tmin:array[0..maxn] of integer;

  procedure Fopen;
  begin
    assign(input,'hjjhvf.in');
    reset(input);
    assign(output,'hjjhvf.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(n);
    for i:=1 to n do readln(a[i,1],a[i,2],a[i,3],a[i,4]);
  end;

  procedure QSort(p,l,r:integer);
  var
    i,j:integer;
    t,x:integer;
  begin
    i:=l; j:=r;
    x:=a[b[(l+r) shr 1],p];
    repeat
      while a[b[i],p]<x do inc(i);
      while a[b[j],p]>x do dec(j);
      if i<=j then
      begin
        t:=b[i]; b[i]:=b[j]; b[j]:=t;
        inc(i); dec(j);
      end;
    until i>j;
    if l<j then QSort(p,l,j);
    if i<r then QSort(p,i,r);
  end;

  function lowbit(x:integer):integer;
  begin
    exit(x and (-x));
  end;

  function min(a,b:integer):integer;
  begin
    if a<b then exit(a) else exit(b);
  end;

  function query(k:integer):integer;
  var
    res:integer;
  begin
    res:=n shl 1;
    while k>0 do
    begin
      res:=min(res,tmin[k]);
      dec(k,lowbit(k));
    end;
    exit(res);
  end;

  procedure update(k,x:integer);
  begin
    while k<=n do
    begin
      tmin[k]:=min(tmin[k],x);
      inc(k,lowbit(k));
    end;
  end;

  procedure GoOut(p1,p2,p3:integer);
  var
    i,q:integer;
  begin
    for i:=1 to n do b[i]:=i;
    QSort(p1,1,n);
    for i:=0 to n do tmin[i]:=n shl 1;
    for i:=1 to n do
    begin
      q:=query(a[b[i],p2]-1);
      if q<a[b[i],p3] then fall[b[i]]:=true;
      update(a[b[i],p2],a[b[i],p3]);
    end;
  end;

  procedure Solve;
  var
    i:integer;
  begin
    fillchar(fall,sizeof(fall),false);
    GoOut(1,2,3);
    GoOut(2,3,4);
    GoOut(1,3,4);
    GoOut(1,2,4);
    m:=0;
    for i:=1 to n do if fall[i] then inc(m);
    writeln(m);
    for i:=1 to n do if fall[i] then writeln(i);
  end;

begin
  Fopen;
  Init;
  Solve;
  Fclose;
end.