Cod sursa(job #610986)
#include <fstream.h>
int N, v[100], i, j, nr = 0, auxiliar, auxiliar2;
void citire ()
{
ifstream fin ("nrtri.in");
fin >> N;
for (i = 0; i < N; i++)
{
fin >> v[i];
}
fin.close ();
}
int c_binara (int val, int capat)
{
int i, step;
for (step = 1; step <= capat; step <<= 1);
for (i = 0; step; step >>= 1)
{
if (i + step <= capat && v[i + step] <= val) i += step;
}
return i;
}
void qsort (int l1, int l2)
{
int pivot = 0, l1a = l1, l2a = l2;
if (l1 >= l2) return;
while (l1 < l2)
{
if (v[l1] > v[l2])
{
auxiliar = v[l1];
v[l1] = v[l2];
v[l2] = auxiliar;
if (pivot)
{
pivot = 0;
l2--;
}
else
{
pivot = 1;
l1++;
}
}
else
{
if (pivot) l1++;
else l2--;
}
}
qsort (l1a, l1 - 1);
qsort (l1 + 1, l2a);
}
void treaba (int index)
{
for (i = 0; i < index; i++)
{
auxiliar = v[index] - v[i];
auxiliar2 = c_binara (auxiliar, i);
nr += i - auxiliar2;
}
}
void scriere ()
{
ofstream fout ("nrtri.out");
fout << nr;
fout.close ();
}
int main ()
{
citire ();
if (N < 3)
{
scriere ();
return 0;
}
qsort (0, N - 1);
for (j = 2; j < N; j++)
{
treaba (j);
}
scriere ();
return 0;
}