pz12_gavrilov

commit 07cf302e53d7e79057c0ed866be7eb87adde09bb
parent fd3098818a67d9a39339789a06c1f5abc68314e7
Author: Plat <plat@stellar-nexus.ru>
Date:   Wed, 26 Nov 2025 21:59:35 +0000

More optimizations

Diffstat:
M
knapsack.c
 | 
41
++++++++++++++++++++++++-----------------
M
sort.c
 | 
32
+++++++++++++++++++++++++-------
M
sort_single.c
 | 
4
++--

3 files changed, 51 insertions(+), 26 deletions(-)
diff --git a/knapsack.c b/knapsack.c
@@ -10,35 +10,42 @@ knapsack_bell(unsigned int k,    unsigned int w,
               unsigned int m[k], unsigned int c[k],
               BitChunk out[k/64+1])
 {
-	unsigned int (*opt)[w+1] = malloc(sizeof(*opt) * (k+1));
-	if (!opt) {
+	unsigned int *dp = calloc((w + 1) * (k + 1), sizeof(*dp));
+	if (!dp) {
 		errno = ENOMEM;
 		return -1;
 	}
 
-	for (unsigned int i = 0; i <= k; ++i) {
+	for (unsigned int i = 1; i <= k; ++i) {
+		unsigned int weight = m[i-1];
+		unsigned int cost   = c[i-1];
 		for (unsigned int wi = 0; wi <= w; ++wi) {
-			if (i == 0 || wi == 0)
-				opt[i][wi] = 0;
-			else if (m[i-1] > wi)
-				opt[i][wi] = opt[i-1][wi];
-			else
-				opt[i][wi] = MAX
-				(
-				opt[i-1][wi],
-				c[i-1] + opt[i-1][wi - m[i-1]]
-				);
+			unsigned int prev = dp[(i-1)*(w+1) + wi];
+			if (wi >= weight) {
+				unsigned int alt =
+				 dp[(i-1)*(w+1) + (wi - weight)] + cost;
+				dp[i*(w+1) + wi] = MAX(alt, prev);
+			} else {
+				dp[i*(w+1) + wi] = prev;
+			}
 		}
 	}
 
+	unsigned int wi = w;
 	for (unsigned int i = k; i > 0; --i) {
-		if (opt[i][w] != opt[i-1][w]) {
-			SET(out, i - 1);
-			w -= m[i-1];
+		unsigned int w_row   = i*(w+1);
+		unsigned int prevrow = (i-1)*(w+1);
+		if (dp[w_row + wi] != dp[prevrow + wi]) {
+			SET(out, i-1);
+			wi -= m[i-1];
+		} else {
+			UNSET(out, i-1);
 		}
+		if (wi == 0)
+			break;
 	}
 
-	free(opt);
+	free(dp);
 	return 0;
 }
 
diff --git a/sort.c b/sort.c
@@ -1,17 +1,23 @@
+#include <math.h>
+
 void
 bubble_sort(unsigned int n, int a[n])
 {
 	int tmp;
 	for (unsigned int i = 0; i < n - 1; ++i) {
-		for (unsigned int j = 0; j < n - i - 1; ++j) {
+		int swapped = 0;
+		unsigned int limit = n - i - 1;
+		for (unsigned int j = 0; j < limit; ++j) {
 			if (a[j] > a[j+1]) {
 				tmp = a[j];
 				a[j] = a[j+1];
 				a[j+1] = tmp;
+				swapped = 1;
 			}
 		}
+		if (!swapped)
+			break;
 	}
-
 }
 
 void
@@ -19,14 +25,16 @@ choice_sort(unsigned int n, int a[n]) /* it's actually selection_sort :nerd: */
 {
 	int tmp;
 	for (unsigned int i = 0; i < n - 1; ++i) {
-		int min = i;
+		unsigned int min = i;
 		for (unsigned int j = i + 1; j < n; ++j) {
 			if (a[j] < a[min])
 				min = j;
 		}
-		tmp = a[i];
-		a[i] = a[min];
-		a[min] = tmp;
+		if (min != i) {
+			tmp = a[i];
+			a[i] = a[min];
+			a[min] = tmp;
+		}
 	}
 }
 
@@ -46,8 +54,18 @@ insert_sort(unsigned int n, int a[n])
 void
 shell_sort(unsigned int n, int a[n])
 {
+	unsigned int gaps[32];
+	unsigned int count = 0;                 /* Tokuda gaps */
+	for (unsigned int k = 1;; ++k) {
+		double hk = ceil((pow(9.0,k)-pow(4.0,k))/(5.0*pow(4.0,k-1)));
+		if (hk >= n)
+			break;
+		gaps[count++] = (unsigned int)hk;
+	}
+
 	int tmp;
-	for (unsigned int gap = n/2; gap > 0; gap /= 2) {
+	for (int gi = count - 1; gi >= 0; --gi) {
+		unsigned int gap = gaps[gi];
 		for (unsigned int i = gap; i < n; ++i) {
 			tmp = a[i];
 			unsigned int j = i;
diff --git a/sort_single.c b/sort_single.c
@@ -34,12 +34,12 @@ int
 main(int argc, char *argv[])
 {
 	argv0 = argv[0];
-	unsigned int n = input(0, UINT_MAX);
+	unsigned int n = input(2, UINT_MAX);
 	int *arr = emalloc(sizeof(*arr) * n);
 	
 	unsigned int len;
 	for (len = 0; len < n; ++len)
-		arr[len] = input(0, INT_MAX);
+		arr[len] = input(INT_MIN, INT_MAX);
 	
 	clock_t solve_time = clock();
 	sort(n, arr);