Cod sursa(job #1795075)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 1 noiembrie 2016 22:58:16
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#define NMAX 801
#define RADIX_SIZE 8
#define get_byte(x) ((x >> (RADIX_SIZE * byte)) & 0xFF)

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");
int A[NMAX], n;

void CountSort(int A[], int B[], int byte)
{
    int length = (1 << RADIX_SIZE);
    int _count[length];
    int indx[length];
    for (int i = 0; i < length; i++)
        _count[i] = 0;
    for (int i = 1; i <= n; i++)
        _count[get_byte(A[i])]++;
    indx[0] = 1;
    for (int i = 1; i < length; i++)
        indx[i] = indx[i - 1] + _count[i - 1];
    for (int i = 1; i <= n; i++)
        B[indx[get_byte(A[i])]++] = A[i];

}

void RadixSort(int A[], int n)
{
    int *temp = new int[n + 1];
    for (int i = 0; i < 4; i++)
        if (i % 2 == 0)
            CountSort(A,temp,i);
        else
            CountSort(temp,A,i);
    delete[] temp;
}

int binar(int x, int key)
{
    int i = 0, step;
    for (step = 1; step <= key; step <<= 1);
    for (; step; step >>= 1)
        if (x + i + step <= n && A[x + i + step] <= key)
            i += step;
    return i + x;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> A[i];
    in.close();
    RadixSort(A, n);
    int ind;
    long long int nr = 0;
    for (int i = 1; i <= n - 2; i++)
        for (int j = i + 1; j <= n - 1; j++)
        {
            ind  = binar(j + 1, A[i] + A[j]);
            if (A[ind] >= A[i] + A[j])
                nr += (long long)(binar(j + 1, A[i] + A[j]) - j);
        }
    out << nr << "\n";
    return 0;
}