Привет и извините за хромое название этого поста, просто не могу найти лучшего.
Итак, я решаю упражнение Codility под названием NumberOfDiscIntersections. Решение требует некоторой базовой сортировки c и незначительных арифметических операций c. Я достиг 93% результата, и только один тест провалился. Ниже приводится описание, которое они предоставляют:
Например, для ввода [1, 2147483647, 0] решение вернуло неправильный ответ (получил -1, ожидаемое 2).
Проблема видна здесь .
И вот мое решение:
typedef long long int my_type; //can't use unsigned!
#define LIMIT 10000000
//method used by qsort()
int comp(const void* left, const void* right) {
my_type arg1 = *(const my_type*)left;
my_type arg2 = *(const my_type*)right;
if(arg1 < arg2) return -1;
if(arg2 < arg1) return 1;
return 0;
}
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
//allocate two arrays to hold beginning and ending points of each circle
my_type *lower = calloc(N, sizeof(my_type));
my_type *upper = calloc(N, sizeof(my_type));
int i;
my_type count = 0;
//initialize arrays
for(i = 0; i < N; i++) {
lower[i] = i - A[i];
upper[i] = i + A[i];
}
qsort(lower, N, sizeof(my_type), comp);
qsort(upper, N, sizeof(my_type), comp);
int open = 0;
int upper_index = 0;
for(i = 0; i < N; i++) {
while(lower[i] > upper[upper_index]) {
//printf("closing %d\n", upper[upper_index]);
upper_index++;
open--;
}
open++;
count += (open-1);
//printf("opening %d\n", lower[i]);
}
free(lower);
free(upper);
return ((int)count <= LIMIT) ? (int)count : -1;
}