NKLP - Hoán vị dài nhất

Tác giả: RR

Ngôn ngữ: Pascal

//Written by Nguyen Thanh Trung
//O(N) algorithm
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
type
  status        =       record
                                left,right      :       longint;
                                wrong,ln        :       longint;
                        end;
var
  f1,f2         :       text;
  n,kq          :       longint;
  a,dd          :       array[1..MAXN] of longint;
  sum           :       array[-1..MAXN] of int64;
  last,now      :       status;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        begin
          read(f1,a[i]);
          sum[i]:=sum[i-1]+a[i];
        end;
    end;
procedure update;
    var
      i:longint;
    begin
      if now.left<1 then now.left:=1;
      if now.right>n then now.right:=n;
      if last.left<>now.left then
        if last.left<now.left then
          for i:=last.left to now.left-1 do
            begin
              dd[a[i]]-=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=0 then now.wrong+=1;
            end
        else for i:=last.left-1 downto now.left do
            begin
              dd[a[i]]+=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=2 then now.wrong+=1;
            end;
      if last.right<>now.right then
        if last.right>now.right then
          for i:=last.right downto now.right+1 do
            begin
              dd[a[i]]-=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=0 then now.wrong+=1;
            end
        else for i:=last.right+1 to now.right do
            begin
              dd[a[i]]+=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=2 then now.wrong+=1;
            end;
      if now.wrong<>0 then exit;
      if sum[now.right]-sum[now.left-1]<>(int64(now.ln+1)*now.ln)>>1 then exit;
      kq:=max(kq,now.ln);
    end; //update
procedure solve;
    var
      one,x:longint;
      save:status;
    begin
      for one:=1 to n do
        if a[one]=1 then
          begin
            dd[1]:=1;
            with save do
              begin
                left:=one; right:=one;
                ln:=1; wrong:=0;
              end;
            kq:=max(kq,1);
          //TH1: so lon nhat o ben trai so 1
            last:=save;
            x:=one-1;
            while (x>=1) and (a[x]<>1) do
              begin
                with now do
                  begin
                    ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
                    left:=x; right:=x+ln-1;
                  end;
                x-=1; update;
                last:=now;
              end;
            now:=save; update;
          //TH2: so lon nhat o ben phai so 1
            last:=save;
            x:=one+1;
            while (x<=n) and (a[x]<>1) do
              begin
                with now do
                  begin
                    ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
                    right:=x; left:=x-ln+1;
                  end;
                x+=1; update;
                last:=now;
              end;
            now:=save; update;
          end; //for one
    end; //solve

begin
  openF;
  inp;
  kq:=0;
  solve;
  writeln(f2,kq);
  closeF;
end.

Download