summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--šola/p2/dn/DN04b_63230317.c71
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);
}