Lesson 99: ArrayInversionCount (Array Inversion Count)

Lesson 99: ArrayInversionCount
https://codility.com/programmers/lessons/14

ぎりぎりのところまで行ったのですが、友達と食事の時間がせまってたので、食事中に考えてフラストレーションがたまったりしないようにググってしまいました。

おそらく、ソートに関する問題でマージソート絡みだろうという直感はあったのですが、最後の１ピースが埋まらずorz

問題は結局自分でマージソート書けばいいのですよね。マージソートを「並列でやらないときは」、両行くの先頭からやっていけば、Q<R とA[Q] > A[R]の判定がソート中に出来ますと言う話でした。

なんか、カチンときたのもあり、皆再帰を使ってるのでループでやっておきました。

で、100%のスコアです。とりあえず、 if (A[lpos] <= A[rpos])で最初＜にしてしまってつまらないバグを出してしまいましたorz

#include<stdio.h>
#include <alloca.h>
#include <memory.h>



int solution(int A[], int N) 
{
    int cnt = 0;
    int memsize = sizeof(int) * N;
    int*work    = (int*)alloca(memsize);
    
    
    for (int blksize = 1; blksize < N; blksize *= 2){
        
        int lpos = 0;
        int rpos = blksize;

        //merge each blocks
        while(lpos <= N){
            int writebackpos = lpos;
            
            int lend = lpos + blksize;
            lend = lend >= N ? N : lend;
            
                        
            int rend = rpos + blksize;
            rend = rend >= N ? N : rend;

            //merge
            int wpos = 0;
            while (lpos < lend && rpos < rend){
                if (A[lpos] <= A[rpos]){
                    work[wpos++] = A[lpos++];
                }
                else {
                    work[wpos++] = A[rpos++];
                    cnt += lend - lpos;
                    if (cnt >=  1000000000){
                        return - 1;
                    }
                }
            }
            
            while (lpos < lend){
                work[wpos++] = A[lpos++];
            }

            while (rpos < rend){
                work[wpos++] = A[rpos++];
            }

            //write back
            memcpy(A + writebackpos, work, sizeof(int) * wpos);

            //proceed to the next block
            lpos = rpos;
            rpos = lpos + blksize;
        }

    }
   
    return cnt;
}