Cod sursa(job #1515603)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 1 noiembrie 2015 21:41:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <algorithm>
const int nmax = 805;
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int v[nmax], sum = 0, n;

void secondaryBinarySearch(int lmtR) {
    int x, lmtL;
    x = v[lmtR];
    lmtL = 1;
    while (true) {
        int pivot;
        pivot = (lmtL + lmtR) / 2;
        if (v[pivot] < x)
            lmtL = pivot;
        if (v[pivot] == x) {
            if (v[pivot - 1] != v[pivot])
                sum += n - pivot - 1;
            lmtR = pivot;
        }
    }
}

void binarySearch(int lmtL, int lmtR, int x) {
    while (true) {
        int pivot;
        pivot = (lmtL + lmtR) / 2;
        if (v[pivot] * 2 >= v[x]) {
            if (v[pivot - 1] * 2 < v[x] and v[pivot] * 2 != v[x]) {
                secondaryBinarySearch(pivot);
                return;
            }
            else if (v[pivot - 1] * 2 < v[x] and v[pivot] * 2 == v[x]) {
                sum += n - pivot - 1;
                return;
            }
            lmtR = pivot;
        }
        else if (v[pivot] * 2 < v[x])
            lmtL = pivot;
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    sort(v + 1, v + n + 1);
    for (int i = n; i >= 1; --i) {
        binarySearch(1, n - 1, i);
    }
    fout << sum;
    return 0;
}