Codility/CountTriangles at master · vvitkovsky/Codility · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 100% solution
#include <algorithm>

int solution(vector<int> &A) {

    std::sort(A.begin(), A.end());

    int n = A.size();
    int result = 0;

    for (int x = 0; x < n; ++x) {
        int y = x + 1;
        int z = x + 2;

        while (z < n) {
            if (A[x] + A[y] > A[z]) {
                result += z - y;
                z++;
            }
            else if (y < z - 1) {
                y++;
            }
            else {
                y++;
                z++;
            }
        }
    }
    return result;
}

// 100% solution
#include <algorithm>

int solution(vector<int> &A) {

    std::sort(A.begin(), A.end());
    size_t n = A.size();
    int result = 0;

    for (size_t x = 0; x < n; ++x) {
        size_t z = x + 2;
        for (size_t y = x + 1; y < n; ++y) {
            while (z < n && A[x] + A[y] > A[z]) {
                z++;
            }
            result += z - y - 1;
        }
    }
    return result;
}