Pagini recente » Cod sursa (job #1831554) | Cod sursa (job #1516704) | Cod sursa (job #934901) | Cod sursa (job #1966393) | Cod sursa (job #1515603)
#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;
}