Cod sursa(job #2614882)

Utilizator stanciucalinStanciu Calin stanciucalin Data 12 mai 2020 19:58:57
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n, cnt;
int arr[805];

void interclasare(int st1, int dr1, int st2, int dr2){

    int i = st1;
    int j = st2;

    int k = 0;

    int * auxarr = new int[dr1 - st1 + dr2 - st2 + 5];

    while(i <= dr1 && j <= dr2){

        if(arr[i] <= arr[j]){

            auxarr[k] = arr[i];
            i += 1;
        }
        else{

            auxarr[k] = arr[j];
            j += 1;
        }
        k += 1;
    }

    while(i <= dr1){

        auxarr[k] = arr[i];
        i += 1;
        k += 1;
    }

    while(j <= dr2){

        auxarr[k] = arr[j];
        j += 1;
        k += 1;
    }

    for(int i = 0; i < k; i++)
        arr[st1 + i] = auxarr[i];

    delete[] auxarr;
}

void mergesort(int st, int dr){

    if(st >= dr)
        return;

    int m = (st + dr) / 2;

    mergesort(st, m);
    mergesort(m + 1, dr);

    interclasare(st, m, m + 1, dr);
}

int binarysearch(int x, int i, int j){

    while(i < j){

        int m = i + (j - i) / 2;

        if(arr[m] <= x){

            i = m + 1;
        }
        else{

            j = m;
        }
    }

    if(arr[(i + j) / 2] > x)
        return ((i + j) / 2) - 1;

    return j;
}

int main(){

    f>>n;

    for(int i = 0; i < n; i++)
        f>>arr[i];

    mergesort(0, n - 1);

    for(int i = 0; i < n - 2; i++)
        for(int j = i + 1; j < n - 1; j++){

            int k = binarysearch(arr[i] + arr[j], j + 1, n - 1);

            if(k >= 0){

                cnt += k - j;
            }
        }

    g<<cnt;

    ///cout<<binarysearch(25, 0, 16)<<" "<<binarysearch(30, 0, 16)<<" "<<binarysearch(41, 0, 16)<<" "<<binarysearch(60, 0, 16)<<" "<<binarysearch(68, 0, 16);

    return 0;
}