pz12_gavrilov

commit fd3098818a67d9a39339789a06c1f5abc68314e7
parent 709cc6b9f2baff6339a563620e0eb92183aa6a3c
Author: Plat <plat@stellar-nexus.ru>
Date:   Wed, 26 Nov 2025 00:56:32 +0000

Fixed several mistakes made in the last commit

Diffstat:
M
knapsack.c
 | 
21
+++++++++++++--------
M
knapsack.h
 | 
6
+++---
M
knapsack_single.c
 | 
6
+++---

3 files changed, 19 insertions(+), 14 deletions(-)
diff --git a/knapsack.c b/knapsack.c
@@ -2,6 +2,7 @@
 #include <limits.h>
 #include <stdlib.h>
 
+#include "knapsack.h"
 #include "util.h"
 
 int
@@ -30,14 +31,15 @@ knapsack_bell(unsigned int k,    unsigned int w,
 		}
 	}
 
-	for (; k > 0; --k) {
-		if (opt[k][w] != opt[k-1][w]) {
-			SET(out, k - 1);
-			w -= m[k-1];
+	for (unsigned int i = k; i > 0; --i) {
+		if (opt[i][w] != opt[i-1][w]) {
+			SET(out, i - 1);
+			w -= m[i-1];
 		}
 	}
 
 	free(opt);
+	return 0;
 }
 
 static void
@@ -116,15 +118,18 @@ knapsack_greed(unsigned int k,    unsigned int w,
 			break;
 
 		weight += m[pos];
-		if (weight > w)
+		if (weight > w) {
 			weight -= m[pos];
-		else if (weight < w)
+		} else if (weight < w) {
+			SET(out, pos);
+		} else {
 			SET(out, pos);
-		else
 			break;
+		}
 	}
 
 	free(density);
+	return 0;
 }
 
 int
@@ -152,7 +157,7 @@ knapsack_full(unsigned int k,    unsigned int w,
 			best_cost = cost;
 			out[0] = list; /* this function is not used above 64 
 			                  - abuse this fact */
-			}
 		}
 	}
+	return 0;
 }
diff --git a/knapsack.h b/knapsack.h
@@ -1,8 +1,8 @@
 #include <stdint.h>
 typedef uint64_t BitChunk;
-#define CHECK(arr, bit) ((arr)[(bit/64)] &   (1ULL << ((bit)%64)))
-#define   SET(arr, bit) ((arr)[(bit/64)] |=  (1ULL << ((bit)%64)))
-#define CLEAR(arr, bit) ((arr)[(bit/64)] &= ~(1ULL << ((bit)%64)))
+#define CHECK(arr, bit) ((arr)[((bit)/64)] &   (1ULL << ((bit)%64)))
+#define   SET(arr, bit) ((arr)[((bit)/64)] |=  (1ULL << ((bit)%64)))
+#define CLEAR(arr, bit) ((arr)[((bit)/64)] &= ~(1ULL << ((bit)%64)))
 
 int  knapsack_bell(unsigned int k,    unsigned int w,
                    unsigned int m[k], unsigned int c[k],
diff --git a/knapsack_single.c b/knapsack_single.c
@@ -43,7 +43,7 @@ main(int argc, char *argv[])
 	for (len = 0; len < k; ++len)
 		c[len] = input(0, UINT_MAX);
 	
-	BitChunk *out = ecalloc(sizeof(*out) * (k/64 + 1));
+	BitChunk *out = ecalloc(k/64 + 1, sizeof(*out));
 	clock_t solve_time = clock();
 	if (knapsack(k, w, m, c, out) < 0)
 		eprintf("knapsack:");
@@ -53,10 +53,10 @@ main(int argc, char *argv[])
 	for (len = 0; len + 1 < k; ++len) {
 		if (CHECK(out, len)) {
 			if (saved_number >= 0)
-				printf("%d ", saved_number);
+				printf("%ld ", saved_number);
 			saved_number = len;
 		}
 	}
 	if (saved_number >= 0)
-		printf("%d\n", saved_number);
+		printf("%ld\n", saved_number);
 }