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.