Test results - Codility

Tasks Details

medium

1. ArrayInversionCount

Compute number of inversion in an array.

Task Score

100%

Correctness

100%

Performance

100%

An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].

Write a function:

int solution(int A[], int N);

that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.

For example, in the following array:

A[0] = -1 A[1] = 6 A[2] = 3 A[3] = 4 A[4] = 7 A[5] = 4

there are four inversions:

(1,2) (1,3) (1,5) (4,5)

so the function should return 4.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Solution

Programming language used C

Total time used 48 minutes

Effective time used 48 minutes

Notes

not defined yet

Task timeline

Code: 11:22:24 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid;
        else if ( x < xs[mid] )
            l = mid+1;
        else
            r = mid;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*a), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[0]);
}

Analysis

Compile error

In file included from user.c:23:0:
func.c: In function 'solution':
func.c:28:26: error: 'a' undeclared (first use in this function)
func.c:28:26: note: each undeclared identifier is reported only once for each function it appears in
func.c:33:1: warning: control reaches end of non-void function [-Wreturn-type]

Code: 11:22:35 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid;
        else if ( x < xs[mid] )
            l = mid+1;
        else
            r = mid;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[0]);
}

Analysis

expand all Example tests

▶

example1
example test

✘

TIMEOUT ERROR
running time: >11.00 sec., time limit: 8.00 sec.

11.000 s

TIMEOUT ERROR, running time: >11.00 sec., time limit: 8.00 sec.

Code: 11:25:06 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l < r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid;
        else if ( x < xs[mid] )
            l = mid+1;
        else
            r = mid;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

expand all Example tests

▶

example1
example test

✘

TIMEOUT ERROR
running time: >11.00 sec., time limit: 8.00 sec.

11.000 s

TIMEOUT ERROR, running time: >11.00 sec., time limit: 8.00 sec.

Code: 11:28:15 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l < r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid;
        else if ( x < xs[mid] )
            r = mid
        else
            l = mid+1;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

Compile error

In file included from user.c:23:0:
func.c: In function 'bs':
func.c:18:9: error: expected ';' before 'else'

Code: 11:28:24 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l < r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

expand all Example tests

▶

example1
example test

✘

TIMEOUT ERROR
running time: >11.00 sec., time limit: 8.00 sec.

11.000 s

TIMEOUT ERROR, running time: >11.00 sec., time limit: 8.00 sec.

Code: 11:29:16 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l < r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, l=mid+1;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 4

0.004 s

WRONG ANSWER, got 0 expected 4

stdout:

Code: 11:29:33 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, l=mid+1;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 4

0.008 s

WRONG ANSWER, got 0 expected 4

stdout:

Code: 11:30:24 UTC, c, verify, result: Failed

show code in pop-up

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

#define MAX_N (100000)

int ys[MAX_N];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int solution(int * xs, int n) {
    int i;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    return 0;
}

Analysis

expand all Example tests

▶

example1
example test

✘

WRONG ANSWER
got 0 expected 4

0.004 s

WRONG ANSWER, got 0 expected 4

stdout:

Code: 11:40:22 UTC, c, verify, result: Failed

show code in pop-up

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 52 53 54

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

int update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1));
        update(xs[i], n);
    }
    return acc;
}

Analysis

Compile error

In file included from user.c:23:0:
func.c: In function 'solution':
func.c:50:30: error: expected ';' before ')' token
func.c:50:30: error: expected statement before ')' token
user.c: In function 'update':
func.c:38:1: warning: control reaches end of non-void function [-Wreturn-type]

Code: 11:40:37 UTC, c, verify, result: Failed

show code in pop-up

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 52 53 54

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

int update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]);
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

Analysis

expand all Example tests

▶

example1
example test

✘

TIMEOUT ERROR
running time: >11.00 sec., time limit: 8.00 sec.

11.000 s

TIMEOUT ERROR, running time: >11.00 sec., time limit: 8.00 sec.

Code: 11:41:34 UTC, c, verify, result: Passed

show code in pop-up

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 52 53 54

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=0; i < n; ++i )        
        printf("%d\n", xs[i]);
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

stdout:

WARNING: producing output may seriously slow down your code!
1
5
2
3
6
3

Code: 11:41:51 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

Code: 11:49:01 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 0

Code: 11:49:16 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 0

Code: 11:49:25 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 0

Code: 11:49:35 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 0

Code: 11:50:17 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 10

Code: 11:50:23 UTC, c, verify, result: Passed

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

User test case 1:

None

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data0

✔

0.004 s

OK
function result: 10

Code: 11:50:25 UTC, c, final, score: 100

show code in pop-up

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 52

#define MAX_N (100000)

int ys[MAX_N];
int ft[MAX_N+1];

int cmp(const void * arg1, const void * arg2) {
    return *(const int *)arg1 - *(const int *)arg2;
}

int bs(int * xs, int l, int r, int x) {
    int mid, best = -1;
    
    while ( l != r ) {
        mid = (l + r) / 2;
        if ( xs[mid] == x )
            best = mid, r = mid;
        else if ( x < xs[mid] )
            r = mid;
        else
            l = mid+1;
    }
    return best;
}

int query(int x) {
    int i,acc;
    
    for ( i=x,acc=0; i > 0; i -= (i & -i) )
        acc += ft[i];
    return acc;
}

void update(int x, int n) {
    int i;
    
    for ( i=x; i <= n; i += (i & -i) )
        ft[i] += 1;
}

int solution(int * xs, int n) {
    int i,acc;
    
    memcpy(ys, xs, n*sizeof(*xs));
    qsort(ys, n, sizeof(*xs), cmp);
    for ( i=0; i < n; ++i )
        xs[i] = bs(ys, 0, n, xs[i]) + 1;
    for ( i=n-1,acc=0; i >= 0; --i ) {
        acc += query(xs[i]-1);
        update(xs[i], n);
    }
    return acc;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N))

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all Correctness tests

▶

simple1

✔

0.004 s

▶

simple2

✔

0.004 s

▶

simple3

✔

0.004 s

▶

extreme_0_inv
[0], [], [1,2,3], [1,1,1]

✔

0.004 s

▶

medium1
n=100

✔

0.004 s

▶

medium2
n=200

✔

0.004 s

expand all Performance tests

▶

medium3
n=1000

✔

0.004 s

▶

big1
n=10000

✔

0.012 s

▶

big2
n=20000

✔

0.020 s

▶

big3
n=30000

✔

0.028 s