Cod sursa(job #1589164)

Utilizator RazvanatorHilea Razvan Razvanator Data 3 februarie 2016 20:06:03
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int v[801],n,sum;

void QuickSort(int left,int right,int v[800])
{
    int poz=v[(left+right)/2];
    int i=left,j=right,man;
    while (i<=j) {
        while (v[i]<poz) i++;
        while (v[j]>poz) j--;
        if (i<=j) {
            man=v[i];
            v[i]=v[j];
            v[j]=man;
            i++;
            j--;
        }
    }
    if (i<right) QuickSort(i,right,v);
    if (left<j) QuickSort(left,j,v);
}

int caut_bin(int x,int m)
{
    int pas=1<<10,i=0,s=0;
    while (pas!=0) {
        if (x>=v[i+pas+m] && i+pas+m<n) {s=s+i;i+=pas;cout<<x<<' '<<v[pas+i+m]<<'\n';}
        pas/=2;
    }
    return s;
}

int main()
{
    fin>>n;
    int x;
    for (int i=1;i<=n;i++) fin>>v[i];
    QuickSort(1,n,v);
    for (int i=1;i<=n;i++) {
        for (int j=i+1;j<=n;j++) {
            x=v[i]+v[j];
            sum+=caut_bin(x,i);
        }
    }
    fout<<sum-1;
}