From bba81a6b6efb73c428fa96cd75f5960d2a9c5ce5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= <anton@sijanec.eu>
Date: Sun, 24 Mar 2024 13:51:59 +0100
Subject: =?UTF-8?q?dn04b=20la=C5=BEje=20berljiv?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 "\305\241ola/p2/dn/DN04b_63230317.c" | 71 +++++++++++++++++++-----------------
 1 file changed, 38 insertions(+), 33 deletions(-)

(limited to 'šola/p2/dn')

diff --git "a/\305\241ola/p2/dn/DN04b_63230317.c" "b/\305\241ola/p2/dn/DN04b_63230317.c"
index 105890a..eba57c4 100644
--- "a/\305\241ola/p2/dn/DN04b_63230317.c"
+++ "b/\305\241ola/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);
 }
-- 
cgit v1.2.3