Cod sursa(job #2908294)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 2 iunie 2022 18:10:30
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
 
unsigned int vec[800];
 
void QuickSort(unsigned int* arr, unsigned int num) {
    if(num < 2)
        return;
 
    unsigned int pivot = arr[0];
    unsigned int arr1[800], arr2[800];
    unsigned int num1 = 0, num2 = 0;
 
    for(unsigned int i = 1; i < num; ++i)
        if(arr[i] < pivot)
            arr1[num1++] = arr[i];
        else
            arr2[num2++] = arr[i];
    
    QuickSort(arr1, num1);
    QuickSort(arr2, num2);
 
    unsigned int ind = 0;
    for(unsigned int i = 0; i < num1; ++i)
        arr[ind++] = arr1[i];
    arr[ind++] = pivot;
    for(unsigned int i = 0; i < num2; ++i)
        arr[ind++] = arr2[i]; 
}
int main() {
    std::ifstream fin("nrtri.in");
    std::ofstream fout("nrtri.out");
 
    unsigned int n;
    fin >> n;
 
    for(unsigned int i = 0; i < n; ++i)
        fin >> vec[i];
    QuickSort(vec, n);
 
    unsigned int num = 0;
    for(unsigned int i = 0; i < n - 2; ++i)
        for(unsigned int j = i + 1; j < n - 1; ++j) {
            unsigned int sum = vec[i] + vec[j];
 
            unsigned int start = j + 1, end = n;

            while(start != end) {
                unsigned int mid = (start + end) >> 1;

                if(vec[mid] <= sum)
                    start = mid + 1;
                else
                    end = mid;
            }

            num += start - j - 1;
        }
    fout << num;
 
    fin.close();
    fout.close();
 
    return 0;
}