Cod sursa(job #1795112)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 1 noiembrie 2016 23:35:56
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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 = x - 1, step;
    for (step = 1; step <= (n - x); step <<= 1);
    for (; step; step >>= 1)
        if (i + step <= n && A[i + step] <= key)
            i += step;
    return i;
}

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 (ind >= j + 1)
                nr += (long long)(ind - j);
        }
    out << nr << "\n";
    return 0;
}