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;
}
