MCHAOS - Chaos Strings

Tác giả: ll931110

Ngôn ngữ: Pascal

Program MCHAOS;
{$inline on}
Const
  input  = '';
  output = '';
  maxn = 100000;
Var
  n: longint;
  res: int64;
  s: array[1..maxn] of string[10];
  a: array[1..maxn] of longint;
  pos: array[1..maxn] of longint;

Procedure init;inline;
Var
  f: text;
  i: longint;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do readln(f, s[i]);

  Close(f);
End;

Procedure swap(i,j: longint);inline;
Var
  ts: string[10];
  tpos: longint;
Begin
  ts:= s[i];
  s[i]:= s[j];
  s[j]:= ts;

  tpos:= pos[i];
  pos[i]:= pos[j];
  pos[j]:= tpos;
End;

Procedure quicksort;

  Procedure partition(l,h: longint);inline;
  Var
    i,j: longint;
    p: string[10];
  Begin
    If l >= h then exit;
    i:= l;
    j:= h;
    p:= s[random(h - l + 1) + l];

    Repeat
      While s[i] < p do inc(i);
      While s[j] > p do dec(j);

      If i <= j then
        Begin
          If i < j then swap(i,j);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,n);
End;

Procedure update(v: longint);inline;
Begin
  While v > 0 do
    Begin
      inc(a[v]);
      v:= v - (v and -v);
    End;
End;

Function calc(v: longint): longint;inline;
Var
  t: longint;
Begin
  t:= 0;
  While v <= maxn do
    Begin
      t:= t + a[v];
      v:= v + (v and -v);
    End;
  calc:= t;
End;

Procedure reverse(i: longint);inline;
Var
  ts: string[10];
  j: longint;
Begin
  ts:= '';
  For j:= length(s[i]) downto 1 do ts:= ts + s[i][j];
  s[i]:= ts;
  pos[i]:= i;
End;

Procedure solve;inline;
Var
  i: longint;
Begin
  quicksort;
  For i:= 1 to n do reverse(i);
  quicksort;

  res:= 0;
  For i:= 1 to n do
    Begin
      res:= res + calc(pos[i]);
      update(pos[i] - 1);
    End;
End;

Procedure printresult;inline;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, res);
  Close(f);
End;

Begin
  init;
  solve;
  printresult;
End.

Download