Cod sursa(job #1800865)

Utilizator mihai.alphamihai craciun mihai.alpha Data 8 noiembrie 2016 11:11:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <ctype.h>
FILE *fin, *fout;
#define BUF 1 << 17
char buf[BUF];
long long pos = 0;
//char mat[801][801][801];
inline char next()  {
    if(pos == BUF) fread(buf, 1, BUF, fin), pos = 0;
    return buf[pos++];
}

inline void read(int &x)  {
    char ch;
    x = 0;
    ch = next();
    while(!isdigit(ch)) ch = next();
    while(isdigit(ch))  {
        x = x * 10 + ch - '0';
        ch = next();
    }
    return;
}
int v[801];

bool cmp(int a, int b)  {
    return a < b;
}
int n;
#define L 16
inline int caut1(int x, int st)  {
    int r = st;
    int pos = 1 << L;
    while(pos)  {
        if(r + pos <= n && v[r + pos] <= x)
            r += pos;
        pos /= 2;
    }
    if(r > n || v[r] > x)
    return 0;
    return r - st + 1;
}

int main()  {
    int i, j, rasp = 0, sum, ind1, ind2;
    fin = fopen("nrtri.in", "r");
    read(n);
    for(i = 1;i <= n;i++)
        read(v[i]);
    std::sort(v + 1, v + n + 1, cmp);
    fclose(fin);
    fout = fopen("nrtri.out", "w");
    for(i = 1;i < n;i++)
        for(j = i + 1;j <= n;j++)  {
            sum = v[i] + v[j];
            rasp += caut1(sum, j + 1);
//                for(int k = ind1;k <= ind2;k++)
//                    mat[i][j][k] = 1;
        }
    fprintf(fout, "%d", rasp);
    fclose(fout);
    return 0;
}