Cod sursa(job #2928839)

Utilizator EasyTnsEasyTns EasyTns Data 23 octombrie 2022 22:44:46
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>
#include<algorithm>
//#include<iostream>
using namespace std;
class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};
InParser cin("nrtri.in");
ofstream cout("nrtri.out");
int a[900];
int cautare(int st,int n,int val)
{
  int i=0,step;
  for(step=1;step<=n;step<<=1);
  for(i=st-1;step;step>>=1)
  {
      if(i+step<=n&&a[i+step]<=val)
      {i+=step;}

  }


return i;

}
int main()
{
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++)
    cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
    cnt=cnt+cautare(j+1,n,a[i]+a[j])-j;
}
cout<<cnt;
}