Cod sursa(job #2034389)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 7 octombrie 2017 19:07:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, v[801], cnt;
int pas, indice1, nr_format1, indice2, nr_format2;

int main(){
	in >> n;

	for (int i = 1; i <= n; ++ i)
		in >> v[i];


	sort(v, v + n + 1);


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

      pas = 1;
      pas = pas << 32 - __builtin_clz(n) - 1;
      nr_format1 = 0;
      nr_format2 = 0;

      for (pas; pas > 0; pas = pas >> 1){
      	indice1 = nr_format1 + pas;
      	indice2 = nr_format2 + pas;

      	if (indice1 <= n && v[indice1] <= v[i] + v[j] && v[i] <= v[indice1] + v[j] && v[j] <= v[indice1] + v[i])
      		nr_format1 += pas;
        if (indice2 <= n && (v[indice2] > v[i] + v[j] || v[i] > v[indice2] + v[j] || v[j] > v[indice2] + v[j]))
          nr_format2 += pas;
      }

      if (nr_format1 <= j)
      	continue;
      else{
      	if (nr_format2 > nr_format1)
          cnt += nr_format1 - j;
        else{
          if (nr_format2 <= j)
            cnt += nr_format1 - j;
          else
            cnt += nr_format1 - nr_format2 + 1;
        }
      }

		}
	}

	out << cnt;

	return 0;
}