Cod sursa(job #2886629)

Utilizator dfettiDaniel Fetti dfetti Data 7 aprilie 2022 23:04:08
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

#define DIM 801

int n;
int A[DIM];

inline void swap(int* a, int* b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

int partition(int* v, int lo, int hi)
{
    int pivot = v[hi];
    int i = lo - 1;

    for (int j = lo; j <= hi - 1; ++j)
    {
        if (v[j] < pivot)
        {
            i++;
            swap(&v[i], &v[j]);
        }
    }

    swap(&v[i + 1], &v[hi]);
    return i + 1;
}

void quic_sort(int* v, int lo, int hi)
{
    if (lo >= hi)
        return;

    int p = partition(v, lo, hi);
    quic_sort(v, lo, p - 1);
    quic_sort(v, p + 1, hi);
}

int binary_search(int lo, int hi, int x)
{
    int med = 0;
    int p = lo - 1;
    while (lo <= hi)
    {
        med = (hi + lo) / 2;

        if (A[med] <= x)
        {
            lo = med + 1;
            p = med;
        }
        else
            hi = med - 1;
    }

    return p;
}

int main()
{
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> A[i];

    quic_sort(A, 0, n - 1);

    int count = 0;
    for (int i = 0; i < n - 2; ++i)
        for (int j = i + 1; j < n - 1; ++j)
        {
            int ma = A[i] + A[j];
            int p = binary_search(j + 1, n - 1, ma);
            count += p - j;
        }

    fout << count;

    return 0;
}