diff options
| -rw-r--r-- | šola/p2/dn/DN04b_63230317.c | 71 |
1 files changed, 38 insertions, 33 deletions
diff --git a/šola/p2/dn/DN04b_63230317.c b/šola/p2/dn/DN04b_63230317.c index 105890a..eba57c4 100644 --- a/šola/p2/dn/DN04b_63230317.c +++ b/šola/p2/dn/DN04b_63230317.c @@ -1,39 +1,44 @@ #include <stdio.h> #include <stdbool.h> +#include <limits.h> +#include <stdlib.h> int main (void) { - int n, k, s = 0; - scanf("%d %d", &n, &k); - int a[n]; - for (int i = 0; i < n; i++) - scanf("%d", &a[i]); - int d, l = n-1; - for (int i = 0; i < n-1; i++) - if (2*a[i] <= k && 2*a[i+1] > k) - l = i; - d = l; - fprintf(stderr, "l je %d, d je %d\n", l, d); + unsigned long long n, k; + unsigned long long s = 0; + scanf("%llu %llu", &n, &k); + unsigned long long * števila = calloc(n+1, sizeof *števila); + unsigned long long * količine = calloc(n+1, sizeof *količine); + int unikatnih = 0; + for (unsigned long long i = 0; i < n; i++) { + unsigned long long element; + scanf("%llu", &element); + if (!unikatnih || števila[unikatnih-1] != element) { + količine[unikatnih] = 1; + števila[unikatnih++] = element; + } else + količine[unikatnih-1]++; + } + int l = 0; + int d = unikatnih-1; do { - if (a[l]+a[d] == k) { - int lc = l; - int dc = d; - int add = 0; - while (lc >= 0 && a[lc] == a[l]) - lc--; - while (dc <= n-1 && a[dc] == a[d]) - dc++; - if (a[l] == a[d]) // (dc-lc) choose 2 - add = ((dc-lc-1)*n)/2; - else - add = (d-dc+1)*(lc-l+1); - fprintf(stderr, "l=%d, d=%d, a[l]=%d, a[d]=%d, lc=%d, dc=%d, add=%d\n", l, d, a[l], a[d], lc, dc, add); - l = lc; - d = dc; - s += add; + if (števila[l] + števila[d] == k) { + if (števila[l] == števila[d]) { + s += (količine[l]-1)*(količine[l])/2; + break; + } + s += količine[l]*količine[d]; + if (l == d-1) + break; + l++; + d--; + continue; } - if (l-1 >= 0) - l--; - if (d+1 < n) - d++; - } while (d < n-1 || l > 0); - printf("%d\n", s); + if (l == d) + break; + if (števila[l]+števila[k] < k) + l++; + else + d--; + } while (true); + printf("%llu\n", s); } |